Pathfinding on Android

Excellent examples as always muddy & crusher. I was contemplating if you might have done an A* version in the past maybe? I'm currently doing one myself and would certainly enjoy comparing functions.

For example I use a secondary array to list adjacent nodes to any node in my open list. That secondary array is linked to my primary array by number ID... how did you guys do it? I just ran out of axles more or less.

You seem to disapprove of using such features on android, did the framerate drop substantially while running heuristics?

The only difference between what I've done (which is basically Dijkstra's algorithm) and the A* algorithm, is the use of an heuristic to sort the nodes by distance from the target. That was the reason why I chose to use a list instead of an array (which can't easily be sorted) - although I never got around to it, it should be very easy to do (probably just needs slight changes to 5 lines of code).


I don't have the exporter, so I can't test performance except in Windows. Depending on your specific needs, there are lots of ways to optimize the pathfinding algorithm - for example:

-Single Player vs Zombie Hoard-
In this case, you might want to run your pathfinder to calculate a path to the player from every map tile (like in Crusher's example). The advantage is that you only need to do this once, because all the individual zombies can access the same path data. Speed is going to be proportional to the size of the map - very efficient if you have a small map and tons on zombies; very inefficient if you have a large map with just a few zombies. Also, if you use this method, there's no advantage to using the A* algorithm (in fact, it's not even possible), as the order in which nodes are visited is not important.

-Multiple Baddies Chasing Multiple Targets-
In this case, you could do something similar to above, but as each baddie will be searching for a path to a different location, you will need to run your pathfinder for each of them - so you want to be able to stop searching as soon as you find any path (unless you're using weights, in which case you have to keep searching in case there's a shorter path). Using this method, the A* algorithm could improve performance considerably.

-Fire Emblem / Advance Wars-
In this case, you only move one unit at a time and their movement range is limited, so you definitely want to keep the searched area as small as possible. Having said that, performance shouldn't be an issue anyway, for the very same reasons.


EDIT: I've modified my example so it now uses a best-first search - in other words, it's using the A* algorithm (or something very close to it).
Download: http://sdrv.ms/116vdjA

Interesting post muddymole.
I just finished my A* pathfinding done with only the standard Array. One Array for the open/close Node list and one Array for storing the path for the different NPCs.
- Features unlimited objects (path get calculated Sequentially and short paths will be priorized)
- Works on massive and complex maps and always finds a way (1000*1000 tiles)
- No lag until 150 (*4) calculated tiles (which is about 3-5 Screens)
- if it needs more than 100 tiles, the count of loops get dynamicaly reduced to keep a stady framerate (but it will take exponentialy longer)
- 300-500 tiles it take about 0.5 seconds
- for very large and complex distances, it can take up to 1 minute to get the best path (but no framerate reduction).
- Because I am doing an RPG, the pathfinding time is not THAT important because it is most used for NPCs and can be hidden as "idling" time. But it amazes me how the pathfinding in Starcraft works. :-)
- Another feature is, that if my NPC gets distracted during the path (fight or temporary block), it can easy recalculate the path where it left off.

Questions:
- My main problem is, that I have to loop through the open/closed Array 5 times. 1 time to search for the next (best) tile, and the next 4 times to compare if a surrounding tile is already in the list. How fast is looping through an Array compared to sort an array or use other optimized tactics?
- What are other ways to optimize the A* array for longer distances?

Sounds good.
Is that in Windows? If so, how come you aren't just using an extension?

I haven't tested the performance of sorting using a list vs using an array and fastloops. My guess would be that the list is quicker, as extensions generally are (for example, calculating the distance between objects is quicker using a maths extension than using an expression in MMF2). A list is certainly much simpler.
It's also hard to tell whether your method of using 5 fastloops is more or less efficient. I'm using fewer fastloops, but some of them are nested - so the overall number of calculations at least has the potential to be the same (of course, one or both of us could be doing something wrong).

For very long distances, unless the map is in the form of a maze, there's probably no point finding a path all the way to the destination. Just find a path far enough ahead to be able to avoid small buildings, and update it periodically - it sounds like that might be what you're doing already? In fact, in an RPG, do you even need to be bothering with pathfinding for NPCs that are wandering around miles off screen?


Anyway, what I'm doing (and I'm not saying this is the best method) is this:

1) Pick the tile at top of the list (initially the start tile is the only one in the list).
2) From path_array, find the cost to reach the selected tile using the shortest known route (initially the array is empty).
3) For each of the 4 adjacent tiles, find its weight (from map_array) and add this to the cost to reach our selected tile (found in step 2) - this gives us the total cost to reach each of the adjacent tiles.
4) If the new total costs (found in step 3) are lower than the values already stored in path_array (or if no value is stored) then store the new value, and add the tiles to the list. Also store the path that brought us here in an array (in the form of strings, where 0-3 represent East, North, West, South - eg. 001123 = EENNWS).
5) Remove the selected tile from the list, and sort the remaining items by distance from the destination.

If you're not bothering with variable tile costs (terrain weights), you can obviously simplify that somewhat.

This almost sounds like the WarGame Extension.

Marv

Just chiming in here - I tested your... I think third revision on my phone since I already had the tiles that the unit can move to highlighted and it works without lagging my underpowered phone. There IS something lagging it, but it isn't the pathfinding you made.

Now I'm trying to figure out how to actually make an AI work with it that can detect fences which can be broken to open up new paths and other units which block paths to determine still what the best path would be to the opponent's flag. There is a glitch with the revision I'm using that if there isn't a clear path to the flag or wherever the destination point is, the AI units start moving through obstacles, each other, off the battlefield, etc.

Fences that can be broken:
Broken how exactly? If it were a realtime game, then you could just increase the cost of the tile - for example, if it takes 1 second to move through a square with a cost of 1, and it takes 2 seconds to break through a fence, then set the cost of the fence square to 3. The same would also work if it's a turn-based game and breaking through a fence just costs additional movement points.
If it's turn-based and breaking through a fence ends the turn, then in the part of the pathfinding process where you add the cost of the current tile to the cost of the path up to that point, then instead of looking up the tile's cost from the map array, if it's a fence tile you would just set the cost to however many movement points are remaining. If breaking through a fence could take more than 1 turn (eg. if it has hitpoints, and is attacked in the same way as enemy units), then you'd do the same, but you'd also calculate how many turns it will take to break through the fence, and add a full turn's movement points for each additional turn it will take.

Enemy units:
If you're talking about the AI player deciding how to move it's units, I think the simple answer is just to set enemy units as obstacles (ie. set their cost to the max of 99). Intelligently attacking units in order to open up a path, is very complicated stuff, and probably not worth bothering with (the original Advance Wars didn't bother). You'll find AI in these kinds of games is nearly always reactionary. Instead of having a unit decide where it wants to go, and then afterwards figure out how it can get there, do the opposite - have the unit look at the options immediately available to it, and then pick the best one.

Glitch:
It sounds like you've just made it so the movement event trigger automatically at the end of the pathfinding events, without checking to see if a path was found - should be easy enough for you to fix.

Yeah in the game I'm doing, the fence breaking happens at the end of the turn and ends it when it occurs. Fences sort of have a hitpoint system, but it determines the random chance of breaking it in one turn rather than taking additional breaking turns. Your idea for the reactionary AI is actually one of the options I considered, but at this time I don't know how to make it intelligently pick the best option. I mean I know how I would probably make the AI units move to a fence or player unit, but I don't know how to make it pick the best option until it has an open path to the flag which results in automatic victory.

As for the glitch, I was wondering if there was a way to make it move toward the closed off destination anyway but move as far as it can and then stop at the last open tile. Methinks that would make the enemy AI much easier to implement.

Edit: I got the glitch to stop happening and I'm pretty sure I need to do two different paths on the array for the flag path and the best path until they can reach the flag, but I still don't know how to make it pick the best path. I'm pretty sure I also got the lag to stop happening for when it's on my phone but I'm not sure because I haven't tested it yet. If it has stopped happening, it was because the obstacle check fastloop was running nonstop.

Hey, I have been trying to run MuddyMole's latest example using flash exporter but I am not successful. Since there is no extension used, I cannot pinpoint where the problem is. Could someone tell me what flash limitation is on this specific example ? I would be very grateful to have a fully working extension free flash pathfinding. Thank you !

I tried the latest revision of the pathfinding that MuddyMole made since I have fence that the units have to decide whether to move around or try to break as I said before and it's not working on Android either, my units just go all over the place seemingly at random but they always use the same path.