### Author Topic: Corner detection algorithm  (Read 25651 times)

• Newcomer
• Posts: 10
• Karma: +0/-0
##### Re: Corner detection algorithm
« Reply #15 on: March 28, 2010, 06:55:27 PM »
The problem being that the first example is not a corner.  The middle tile has no diagonal edges exposed.
I would argue that it is a corner by virtue of being the point of intersection of numerous walls:

Code: [Select]
`#..   ..#   ....#. + .#. + .##..#   #..   ...`
But I suppose that's something of a flawed rationale because something like this would be all corners

Code: [Select]
`#########`
So I dunno. Depends on what you're trying to identify corners for. I originally wrote that algorithm to check whether a door or window could be placed on the selected wall segment so it worked fine for that purpose.

#### Darren Grey

• Rogueliker
• Posts: 2027
• Karma: +0/-0
• It is pitch black. You are likely to eat someone.
##### Re: Corner detection algorithm
« Reply #16 on: March 28, 2010, 08:26:49 PM »
I too would like to know the reason for identifying corners.  Seems like an odd thing to check...

#### mike3

• Rogueliker
• Posts: 125
• Karma: +0/-0
##### Re: Corner detection algorithm
« Reply #17 on: March 30, 2010, 10:31:56 AM »
The reason here is to set up cues for the pathfinding algorithm used to dig the tunnels. Namely, it's to prevent stuff like doubled-up tunnels, etc. or at least one possible method to do so. By placing walls that the pathfinder should not dig through in a certain direction, this stuff is prevented.

#### Etinarg

• Rogueliker
• Posts: 424
• Karma: +1/-1
• Idea archivist and game tinkerer.
##### Re: Corner detection algorithm
« Reply #18 on: March 30, 2010, 12:50:29 PM »
I once solved a similar problem with a pattern matching approach. The patterns were 3x3 matrices of characters. For the corner problem I'd assume you need this:

Code: [Select]
`*..##.*..`
And this:

Code: [Select]
`...##.*#.`
. means floor
# means wall
* means anything matches

The matcher code rotated the rule matrices by 0, 90, 180, 270 degrees to see if any of the configuration matches at a location, also mirrored the matrix and did another set of rotations. With that you can check for arbitrary patterns in your map. It's not very fast, but versatile.
« Last Edit: March 30, 2010, 12:59:36 PM by Hajo »