Good way to calculate unit possible moves. (Tile)

Game Play & Game Design
#1

I’ve got a tile based map and I’d like to get a decent method to calculate all the possible squares that the unit may move it.

Lets say that the unit can move 5 spaces.

Each tile has a movement ‘cost’. So some tiles are harder than others to pass through.

Im trying to come up with a good method so that if you click on the unit, it will show all the possible locations the player can move.

I’ve been searching and I keep findind pathfinding A to B algorhythms, but nothing as general as what Im talking about.

I guess I could use A star and calculate the current player square vs every square on the map, but that seems wasteful.

I was trying to figure it out without posting here, but oh well. Hopefully someone else has done this before!

Thanks in advance!

#2

You might want to try implementing a “dijkstra search”, search google for it.

I’ve used it in the past with really good results in comparison to A*. However, you should also be able to use A* with a cap to work out just squares in a certain region.

A* code from Cas: http://www.java-gaming.org/cgi-bin/JGNetForums/YaBB.cgi?board=share;action=display;num=1037669044

Kev

#3

I would suggest the following (correct me if this is stupid): Use a recursive algorithm, always considering the four (or eight) tiles adjacent to the current one. Determine for each if the player can move onto it, and the remaining available ‘movement points’, based on the movement costs for the tile. Store the movement points for the tiles in a 2D array.

Then, do the same for each of the adjacent tiles as center tile. Keep track of already visited tiles, and replace the remaining ‘movement points’ for a tile if the already stored value is higher than the currently calculated value (in that case, you have discovered a cheaper route to the same tile).

If the ‘movement points’ for a tile change, make sure to recalculate all adjacent tiles (you may want to keep track of unvisited / to be recalculated tiles in a list), because their accessibility may have changed, too.

This may sound like a lot of processing, but in reality - depending on the costs of movement and the initially available movement points - the number of reachable tiles (and thus recursions) should be quite low.

#4

Thanks to both of you. I had seen Cas’ code, and researched the “dijkstra Algorhythm”, but I wasnt sure if that would be applied to what I was doing becasue everyone always mentioned it for Point A->B.

I appreciate your idea as well digitprop. I was considering doing something similar, but wasnt sure if it was extremely inefficient.

More input appreciated. I will research Cas’ code some more and look into doing my own method.

#5

[quote]I appreciate your idea as well digitprop. I was considering doing something similar, but wasnt sure if it was extremely inefficient.
[/quote]
It does sound inefficient at first, but it really depends on how far your unit is going to move. If the average move is, like in your example, only 5 spaces, then a simple KISS-style recursive algorithm should do the job. Depth first search (which I think this algorithm is) has, indeed, an exponential order of growth in terms of speed (not too much space is used though). Nevertheless, just like in the traditional Queens problem, the number of choices (again, this depends on how far a unit can move and how expensive the tiles are) will be relatively low at each step.

Now it sounds like I’m repeating what digitprop said. I guess I’m trying to say that Depth first search is not too bad if the number of choices dramatically decreases at some point.

EDIT: add some stuff:
Also, I don’t think speed should matter too much, although it grows exponentially. Computers these days are relatively fast :).
I think the only major problem you could encouter using this (or any) recursive approach is getting too big of a method call stack.

#6

Thanks for your input. Im thinking I’m going to try to implement something like you and digit are talking about. I’d rather have something easy and that I can completely understand rather than a complex algorhythm, at least for now.

Thanks for the tips.

#7

I would keep it as simple as possible if it is not obviously a severe bottleneck. You could even make it pluggable via an interface, so that you can later replace the algorithm easily - if you find that it takes up too much time.

‘Optimize last’, as the XP people say.

#8

Yeah, that makes sense. I can always make it more robust later!!!

PS,

100th post ;o