Hi everyone, I'm working on a 2d tile engine, and using A* for pathfinding. Instead of using every tile as a node, I want to have nodes placed only where they're needed (doorways, corners, etc). I was originally going to do this by manually placing nodes in the map editor, but this would quickly become tedious and is error-prone. I couldn't find any articles on automating this, and after a few days of banging my head against the wall came up this: for every 'walkable' tile on the map if the surrounding 8 tiles match any of these patterns a node isn't needed, otherwise place a node in the middle of the tile the list of patterns looks like this ('-' is walkable, 'O' unwalkable):

- - -     O O O     O - -     - - O     O O O
-   -     O   -     O   -     -   O     -   O
- - -     O - -     O O O     O O O     - - O


O O O     O O O     - - -
-   -     -   -     -   -
- - -     O O O     O O O


O - -     O - O     - - O
O   -     O   O     -   O
O - -     O - O     - - O

...which seems to work fine so far. (Hope that makes sense.) So my question is, are there any articles about this? Are there any common algorithms for doing this? (sorry if this is the wrong forum, I wasn't sure whether to put this here or in game programming since it isn't directly AI related)

It is way too narrow to be worthy of a scientific publication I think, but that doesnt mean it is not a good idea. I used a similar 'pattern' scheme in a programming contest years ago, with great success.

Be sure to check the connectivity between your nodes, and verify is there can be a shortest path between two nodes that is not straight and do not pass through an identified node.

It sounds like the keyword you are looking for is 'visibility graph'. There is quite a bit of research out there on these these, though most of what I have seen has been specific to generation in a polygonal environment. As you are dealing with nodes, there may be some information in the 'probabilistic roadmap' area of research, specifically post generation refinement.

Of course, those may result in much more academic papers than what you are looking for. If your map is going to be very small, you may want to do brute force removal. Basically, go through your list of point and see if you can find any which are redundant by some standard (all of its neighbors connect to each other, it isn't the shortest path to anything, etc). If you can find such a vert, then you could remove it.

Wow, there is a ton of research out there... that's exactly what I was looking for. Thanks for pointing me in the right direction.