A* Pathfinding

[Zefz]

@birdsey: I've implemented your line and point drawing code for debugging into the pathfinding code. There are some issues as you can see (probably an error in my pruning code). Notice what happened to my character icon and inventory in top right corner though. It's caused by your line drawing code.

[Zefz]

Okay, I did some improvements on the pruning code and got the AI to always reach the player eventually. The only problem is that it can use long time to get around corners, as it tries to push itself through them. The good news is that they no longer get stuck.

Here are 2 images showing the slow corner bug:




EDIT:
I solved the issue through making A* only search non-diagonal nodes. This means A* searches in either X or Y direction but not both at the same time. I needed to add some pruning code so that diagonal movement wasn't choppy. It works!

[woodmouse]

Oooh... awesome!

[bgbirdsey]

- The nodes need to be in the center of the tiles, rather than the corners.
- You might want to eliminate diagonal movement, which could speed up the algorithm since there are only 3 new nodes for each open node. The trouble comes in to converting the generated tiles to line segments. I guess you could test every simplification to see if it makes you go inside an invalid area.
- also, the line/point drawing code must have messed with the GL state in some odd way. i thought that I isolated everything, but you never know...

[Zefz]

- The nodes need to be in the center of the tiles, rather than the corners.

Hmm you are correct. I wonder why I hadn't noticed this yet. I wonder why this happens. I guess it is as simple as adding a +(HALF_TILE_SIZE) to every X and Y coordinate?

EDIT:
Did that minor fix and it looks nice now:



Now it remains to see how the performance is when every monster is running A* at the same time.

[bgbirdsey]

Well, it needs to be throttled for sure.
Also, you should check to see if the straight line path is valid before starting A*

[Zefz]

Well, it needs to be throttled for sure.
Also, you should check to see if the straight line path is valid before starting A*

OK I've added this check through your line of sight code. A* is currently throttled to once every half second per object.

Now it would be cool if we could add pits as impassable area for AI, so that they don't charge into a pit if an enemy is on the other side. (maybe a special stoppedby mask for pits that is detected on parsing the mpd file?)

[Seth]

¶ Interesting. Have you tried inserting obstacles inside any mazes?

[bgbirdsey]

you could make all FANOFF tiles definitely off limits. You could also check the max height of a tile's vertices. I believe a bounding box is calculated for every tile, BUT the there is the problem of the difference between tiles and grids (i.e. the ships in Bishopia city harbor).

We could generate a fake bounding box for the grids by scanning through the vertices in the tile definitions and seeing how they actually align with the grids. This would actually work with the current algorithm. Also, if this was done we could add flags, rather than the 8 that are used at present (though I am not saying we should modify or extend the .mpd file format. More like we could differentiate the "closed bit" that is stored in the mpd file from a "closed bit" that is generated by a passage, since the one in the .mpd corresponds to the actual walls)

[Zefz]

Yes. I noticed the problem where A* breaks if the path is through a closed door (i.e impassable area that wasn't impassable when the player moved through it).

[bgbirdsey]

I had an idea for optimizing paths on the way home tonight.

Take the following simple example, where the solution is 2 straight line segments):

where the white area is traverseable, the red area is excluded, the green point is the star and the blue point is the end. The brownish tiles are the tiles returned by A* (which obviously allows diagonal movement).

1. make a "bitmap" that represents the area in question
2. find all areas that will "anitalias" the line (the dark cyan in the pic) and are not excluded
3. start from the 1st tile and draw a straight line between that tile and each successive one until you overlap a white area or a red area.
4. do this for each tile, keeping track of the longest line segment that you have found (the purple lines)
5. when the start tile is no longer part of the "longest segment", you can now record the line and remove all intervening tiles from the waypoint list and start a new search for the longest segment.
6. once you reach the end of the list, repeat the whole process again until you go through the whole algorithm without removing any line segments.

The only question is whether the tip of corners will get shaved off and what to do about large sized objects, but the current algorithm doesn't handle those in any case...

[Zefz]

Are you sure that would be faster? Both use A* to explore traversable nodes so the only difference is the node pruning?

[bgbirdsey]

Faster than what, the current pruning algorithm? I didn't design it for speed, but to reduce a complex set of nodes to the smallest set of waypoints.

Less waypoints is not "better" unless the path requires more waypoints than the character can store. In this case, with no pruning and a dead simple path, 15 waypoints are required. With simple pruning so that horiz and vert waypoints are collapsed, it would require 8 waypoints. With the given algorithm, only 2. The other benefit of converting to the least amount of waypoints is that the character motion appears less jerky.

The real benefit would be with paths that are relatively complex and traverse a lot of open space (as in most of the situations in egoboo dungeons).

[Zefz]

Ah I see. I misunderstood the line where you said you had devised a new method to find "optimized paths"

[Seth]

¶ A problem as of SVN 1550: enemies may attempt to follow you by moving into corners. Please examine this image:

¶ Why could this be happening? Is an obstacle in the middle related to this?