Advance Wars Style Movement

Game Play & Game Design
#1

I am trying to implement a way for a unit to be selected and to be able to highlight the tiles you want to move on and then select the final location and it will move on those tiles. I have achieved this by using a queue and storing each position the selection box hovers over to the queue and then once the final location has been chosen, the unit traverses over the tiles that are stored in the queue, obviously in a FIFO order. This works well and everything is fine, except for the fact of going back on yourself. In advance wars, if you go forward and then decide to move somewhere else you can move back over yourself and then make a new path, even if you do not go back over all of them. I really do not have any idea on how to implement this, any hints or suggestions?

Thanks in advance for your help.

#2

If I were programming, my thought logic would be

  1. Get possible spots (Highlighted Spots)
  2. Keep adding to queue as the cursor moves
  3. If it went backward, take out that last element (May want to consider using arraylist)
  4. If the spot is “out of reach” and inside highlighted, find the shortest path to that point. (Clear queue and recursively find the shortest)
  5. PROFIT!!!

There’s my 2 cents. Good Luck.

Rowdy

#3

You’ll want to use A* or a similar pathfinding method. If it’s grid based, A* is definitely your best bet.

http://www.cokeandcode.com/pathfinding

Basically you store the resulting path in an array and then you just fill in the squares that are part of the path from your position to your target (your target being where your mouse is). Add a little bit of simple image matching and you can have tiles instead of filled squares so you get a nice red arrow-like path just as in Advance Wars.

Also have a look at:
http://www.otcsw.com/maze.php

Run the program in the link above, click the check box “Goal at Mouse” and then move your mouse around and watch the path fill in as you move it. That is done using A*, and you can also use the program I posted to get a good understanding for how a couple different pathfinding algorithms work.

You don’t need to get as complicated as adding to a queue or anything like that. Computers are fast enough these days that you can simply recompute the path every time the goal moves (or even compute it over and over every timestep and I doubt you’d notice any slowdown). You’re only doing this one time (for the selected unit) and not very far (only within their range) and the tiles are relatively large. A* will typically do only 10 to 20 computations for even the most windy area as long as you’re mostly sticking with Advance Wars complexity. Basically if your tiles are bigger than a pixel wide and the units can’t move across the map in a single move, you’re fine.

#4

I did think about recalculating the path everytime, but sometimes there are multiple paths to one spot. So if you wanted to take a path where you wanted to go around a forest instead of going through, all you had to do is move around it (Take the smartest path, not necessarily the shortest). If you need more explaining just ask.

Rowdy

#5

You can just put that in A*'s cost heuristic and it’s computed automatically.