Hello there, I implemented my own A* a few months ago, it is grid based an uses an unordered list to keep the open list, in other words, it is pretty much the worst implementation performance-wise. It is fast enough for my needs, but I want to improve it, I implemented a heap for it and I also wanted to use a region approach.
So far my algorithm converts reagions, those regions turn into a graph, and the A* will operate on this graph. For instance, this input (where 0 means that the tile is not walkable and . means that it is):
000000000
0.......0
0..0....0
0.......0
0.....0.0
0000000.0
Will be converted to this region map:
00 00 00 00 00 00 00 00 00
00 01 01 02 03 03 03 04 00
00 01 01 00 03 03 03 05 00
00 06 06 07 03 03 03 08 00
00 06 06 09 10 11 00 12 00
00 00 00 00 00 00 00 13 00
This is a visual representation of the graph, all the same numbers (but the 00) are a region (every region is a square of size N) that are converted to a node in the graph. Each neighbor region has an edge with the cost so I can run the A* on the graph. The problem is, once I got the A* path, how do I navigate to it?
For instance, If I want to go from region 03 to region 02, I can go directly, but if I am at the botton left part of region 03 and try to go to region 02, I would cross a wall trying to go in a straight line.
Any ideas on how to use this approach? I was trying to do something similar to a navmesh (my game is 2d), to reduce the node number, but I am pretty stuck now.
