Sign in to follow this  
pixelartist

Determining and Displaying All Feasible Movements (Tile Based "Pathing")

Recommended Posts

pixelartist    622
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

Share this post


Link to post
Share on other sites
I would strongly suggest seeing how Chess games are made.

I programmed OpenChess a while back, and the older version highlights squares. There are many ways to find which squares are possible to move. Think of a tree, each branch has a branch. You will want to program your checks like that. Each piece has it's own structure on how it moves across the board, but takes into account if pieces are in the way, ect... You branch out on your checks until you come across your solution for a possible move.

You need to program that check as a function which can be re-used without causing a lot of clutter.

[url="http://www.gamedev.net/blog/1376/entry-2253974-chess-wip-video-more-concept-art/"]OpenChess - OLD VERSION[/url]

[quote]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).[/quote]

Not 100% what you mean here, but if you make the function correctly, it would just use the current tile to check all possible tiles. Just insure it can take into account that unit's attributes, ect... Edited by Black-Rook

Share this post


Link to post
Share on other sites
pixelartist    622
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):

[img]http://dsmedia.ign.com/ds/image/article/915/915684/fire-emblem-shadow-dragon-20081002003132019_640w.jpg[/img]

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.

Share this post


Link to post
Share on other sites
RulerOfNothing    1466
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.[list=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.
[*]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).
[*]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.
[*]Put T on the closed list.
[*]If the open list is empty, finish. Otherwise go back to step 2.
[/list]
This should give all tiles which are reachable by a certain unit, while only checking each tile once.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this