A* - Comparing Paths

Kilgore__Trout

Hi,

Looking for some advice on comparing paths in a tile & turn based game in order to implement basic AI behaviours, such as find nearest player character, as a stepping stone to more advanced behaviours.

For example, there are two player controlled characters in play: A & B. It is enemy E’s turn to move. E has a melee weapon, and is a number of tiles distant from A & B. E wants to find which is closest. A pathfinding request returns a List of tile objects which describe the path from E to A.

E now knows the move cost to A and wants to request a path to B, to see whether moving to A or B has the lowest move cost. It seems that all the tiles need to have their values reset (heuristic, parenting and move cost) in order for the request from E to B to be processed. Any recommendations on storing the first path info while the second is processed doing this?

The obvious solution would seem to be to either 1) create a new set of tile objects to describe the path from E to A, or 2) to create a class to store the information (perhaps a list of Vector2 for the tile positions, and a list of ints for the move cost) and then reset the tile data, process the request, and compare the move costs of the 2 options.

Have started to discover that the obvious solution is often pretty awful, so am curious if either of the above suggestions are semi-sensible, or if you might suggest something else? Thanks for reading!

Retr0gamer

Create a nested array connected to object E. Store the path to A as an array in the nested array and then the path to B. You can store as many as you want until all posible paths are found. There's no need to store them as seperate objects, just coordinates will do or something other signifier if you want to keep the memory and procesing costs down. I'd also store a value that denotes the distance of each path (could be as simple as the amount of tiles to get there). Compare the distance values and pick the path which is shortest.

You can then simplify it once you have that working to speed it up but CPU's are so fast that really if you are doing this 100's of times a frame it should still run fine, CPU's are designed to do this really well.

It's a good programming exercise. Write pathfinding AI for the game I had published was a nightmare but at the end of it it helped me get a lot better and it's esential for if you are ever doing engine or AI design.

Kilgore__Trout

Thanks, did something along these lines, if I understand correctly, but perhaps not as efficient as your solution. Stored each path on E as an object comprised of a list of Vector 2s (for tile positions) and ints (for move cost), and then compare the paths with the move cost at position[0].

You're on the money about it being a challenge : )

It's turn based with a limited amount of units, so the number of requests shouldn't be enormous. Tried doing pathfinding for players real time (path request when mouse moves over a different tile, as opposed to click) and this seems to work well until the paths become very long, but there's likely to be a lot of optimisation available. What all optimisation did you do on yours, and what's the game btw?

First thing will prob be swapping out the insertion sort for ordering the open list by F-cost for a binary heap, which is apparently quite a lot faster.

oisincar

Ok, i could be wrong, but maybe you could implement it like this.

You only do one search, but your heuristic (for the a* search) is the less of the two possible distances. That is,
int heuristic = MIN(dist(a,e), dist(b,e));
or however it looks like in your language. This could of course be expanded easily to account for any number of allied objects.

Then the success conditions for a* would just be find an allied player tile, instead of find the specific tile. Because of how a* works, in my mind at least, this would return the shortest path to the nearest human-player-controlled-tile.

I guess another solution would be to store the path as a series of instructions (I.e. left, down,left, down, left, left... ect). Possibly substitute in numbers for the directions. Could solve the path storing problem? Might not be the most elegant i guess.

Retr0gamer

It's challenging but you will need it. Currently writing a custom collision engine from scratch and pretty much the skills I learnt from path finding are all coming into play as well as for AI.

One thing to test if your AI is slow to find a path is to get rid of all debugging print statements. On my first game I was disgusted to see that if the pathfinding was long it would take about 40 seconds to run it once. After all that work we nearly scraped the game part. Found out removing print statements meant it worked instantaneously. Even on native hardware when it's not printing to console it slowed everything down.

The game I worked on was Harry's Magic Tables on iOS. Not the most amazing game but I coded the entire game section and did most of the bug fixing and had it all completed in 3 months. There were 2 other coders on the project but one had to leave a few days in. The publisher was happy enough to release it as is as well. It was part of a springboard course so made nothing of it but proud of what I did considering I never coded until 6 months before hand.

I figured A* wasn't appropriate for the project so coded a custom pathfinding routine for it. it's less complex than A* but it wouldn't have worked for what we were after. It was a pain because A* is what is always recommended so I had no online tutorial reference so had to come up with it by myself. Had a lot of trouble since Lua has a few quirks when overwriting values in tables which caused a lot of heartache until I figured it out.

If you're pathfinding is taking too long you could fudge it a bit. Just work out shortest distance to an object then path find to it. It might even give the game a little bit of randomness that might improve it, make it seem like the AI is a little unpredictable. There are ways of fudging it a bit. My advice is get it working the brute force way first then think about how you can improve it.

Kilgore__Trout

@ Oisincar: Am only in the early stages of figuring out pathfinding, but it sounds like an efficient way of finding the nearest enemy. Cheers for the idea. Not sure how it might work in a more general system though, if other factors need to be taken into account, like weakest player ally, or player ally with highest damage output. How did you get on with your risk style game, btw?

@ Retr0gamer: Yeah, the pathfinding is going to be one of the basic building blocks for determining how the AI makes decisions, among other things. Had more fun messing around with it than anything else have done in the last few months, but have had to put it aside for now.

Encountered something similar with debug statements. After the initial elation of getting the basics to work, my heart sank when it hung when searching for a longer path. Removing the debug statements helped a lot, and adding basic ordering to the openlist made it faster again. It seems to function fine except for a drop in frames when the player's path is long and is updated in real time (by mousing over a new tile, rather than clicking to fire a pathfinding request).

Looked at XCOM, and there appears to be an interval between when you mouse over a different tile and the path is drawn, so it might be a good place to use a coroutine. Also, could look into restricting player pathfinding to reject requests longer than the player's AP as a way of avoiding the slowdown of finding longer paths. It's early days yet : )

It's quite a leap in 6 months, and a lot of work to get through in 3. Congrats. Sounds like it was a useful experience too.

oisincar

Oh man I typed up a really detailed answer but it self destructed... bleh…

I’ve seen a* before for finding the shortest path for the nearest enemy, but I’m not sure how it would work for other factors to be taken into account. I think it could work like this, say using enemy unit A, and allied units X, and Y. Say A is 6 units from X, and 8 units from Y. But say A is countered by X. One way of looking at those factors would be to add a bonus or penalty to those distances. So A doesn’t want to fight X so badly it would travel 2.5 tiles further to fight a different unit.

I think this could be as simple in code as adding 2.5 to the heuristic for X, so your code now looks like
H = MIN(dist(A,X)+[X getPenalty: X], dist(A,Y)+[X getPenalty: Y]);

That could act strange if X and Y are nearby, when X is added to the fringe but would still have a lower heuristic. Might be fine, as you don’t want A to literally walk past X to get to Y.

My game is going alright, thanks for asking! I’m stuck in 6th year atm, so it’s hard to find energy and time between school, study, and sleeping. Hopefully in the midterm I’ll be able to finally finish it. Fingers crossed!

freelancerTax

Kilgore__Trout wrote: »

@ Oisincar: Am only in the early stages of figuring out pathfinding, but it sounds like an efficient way of finding the nearest enemy. Cheers for the idea. Not sure how it might work in a more general system though, if other factors need to be taken into account, like weakest player ally, or player ally with highest damage output. How did you get on with your risk style game, btw?

@ Retr0gamer: Yeah, the pathfinding is going to be one of the basic building blocks for determining how the AI makes decisions, among other things. Had more fun messing around with it than anything else have done in the last few months, but have had to put it aside for now.

Encountered something similar with debug statements. After the initial elation of getting the basics to work, my heart sank when it hung when searching for a longer path. Removing the debug statements helped a lot, and adding basic ordering to the openlist made it faster again. It seems to function fine except for a drop in frames when the player's path is long and is updated in real time (by mousing over a new tile, rather than clicking to fire a pathfinding request).

Looked at XCOM, and there appears to be an interval between when you mouse over a different tile and the path is drawn, so it might be a good place to use a coroutine. Also, could look into restricting player pathfinding to reject requests longer than the player's AP as a way of avoiding the slowdown of finding longer paths. It's early days yet : )

It's quite a leap in 6 months, and a lot of work to get through in 3. Congrats. Sounds like it was a useful experience too.

you can calculate the path over serval frames you dont need to get the full path on a single timestep.

also make sure you are using a binary heap to store the path lengths if you are using A* - makes it much much faster......

Kilgore__Trout

@ oisincar: I get the geist of your idea, and will look into implementing it when I get back to it. Pretty much in the same position as you, can't really get to work on turned based game right now, but really want to. Keep us posted on your progress.

@ freelancerTax: Cheers, hoping to add both those improvements when get back to it. If I remember, will post results on processing time.