Author Topic: Corner detection algorithm  (Read 20674 times)

Kaskad

  • Newcomer
  • Posts: 10
  • Karma: +0/-0
    • View Profile
    • Email
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.
« Last Edit: March 28, 2010, 06:59:18 PM by Kaskad »

Darren Grey

  • Rogueliker
  • ***
  • Posts: 2027
  • Karma: +0/-0
  • It is pitch black. You are likely to eat someone.
    • View Profile
    • Games of Grey
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
    • View Profile
    • Email
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.
    • View Profile
    • Gedankenweber Blog (German)
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 »