I've poked around the forum a bit and saw some similar topics but most of them are about finding the shortest/most efficient path between two points, whereas I'm looking for ALL of the paths between ALL points that a character can reach

I have a square tile-based map in a Fire Emblem-esque TBS game and I'm trying to figure out the quickest way to determine and highlight all of the squares a given unit can move to when I click on the square it occupies. Each unit has a predetermined number of spaces it can move to in a turn (potentially being affected by terrain, but that's an issue for another time), and movement is to adjacent squares only (not diagonally). Obstacles such as allied units, enemy units and permanent fixtures on the map need to be navigated around (I'll decide later whether or not allied units can be moved through later - it shouldn't add too much work to modify later I hope).

I've got a basic algorithm that looks at every potential path a unit could follow and highlights the tiles along the way, but it's wildly inefficient (to code as well as to run), and it gets progressively messier as the movement range of a unit increases.

The biggest problem I've been seeing over and over is the fact that many tiles can be reached from more than one tile, so progressively expanding the known "reachable area" by looking at each tile only once or twice doesn't seem to work (at least not with any method I've thought of).

Thanks in advance,

Pix

Close but not exactly what I'm looking for. In chess (as I'm sure you know) the pieces cannot navigate around obstacles (ignoring the knight which has limited movement in other aspects), whereas my units are to move one tile at a time to any adjacent tile (let's say up to 5 tiles per turn for now). I'll return to my comparison to the Fire Emblem games because the movement system in that game is the closest comparison I have (this is NOT a screenshot of my game, it's a screenshot I found quickly on the internet and it belongs entirely to the game's creator):



Note that the unit has been selected and each tile it can move to is highlighted in blue. The part you didn't understand was that many of the tiles can be reached via different paths similar to the picture, so checking to see if a specific tile is accessible is difficult if I haven't checked the ones that it is accessible through. The problem is that tiles do not necessarily have to be moved through in any order, so it seems as if some tiles need to be checked simultaneously, while others need to be checked in order.

I might be going about this all wrong, but I don't even know the right Google search terms if I am.

I actually tried the "tree branch" idea though. My initial method was to recursively call a "branch" function and mark each tile that I found to be accessible, but it wouldn't find all of the accessible tiles because I wouldn't recheck marked tiles (hoping to improve runtime). Then I tried it without marking, but its runtime was equivalent to looking for each potential path to each tile which was a few seconds longer than the instant result I was looking for.

Hmm. I think this solution should work (I am assuming here that a tile has the same movement cost no matter where you move into it from):
You need two lists, a 'open' list and a 'closed' list, and keep track of the total movement cost of each tile.

1. Put all tiles immediately accessible to the start tile (i.e. no occupied tiles, impassible tiles or tiles with too high a movement cost) on the open list, with their movement costs.
   
2. Take the tile T with the lowest movement cost off the open list. If there are multiple such tiles, pick one randomly (It shouldn't make any difference here).
   
3. Put the tiles accessible (that is, not occupied, impassible or out of reach) to T which are not already on either list on the open list, and add their movement cost to the total movement cost of T. For example, if T has a movement cost of 6 and the unit can access a plains tile (movement cost 1) and a forest tile (movement cost 3), then add the plains tile with a total movement cost of 7 and the forest tile with a total movement cost of 9. It may help to have a 2D boolean array to allow you to quickly check which tiles have been put on either list.
   
4. Put T on the closed list.
   
5. If the open list is empty, finish. Otherwise go back to step 2.
   

This should give all tiles which are reachable by a certain unit, while only checking each tile once.

Because pixelartist wanted an algorithm to get all tiles accessible from a given tile, and A* most certainly doesn't do this.