# [C++/SFML] Find tiled possible movement

This topic is 1317 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello.

I'm making a turn based strategy game (heavily inspired by advance wars) and I want to implement a tiled movement like in advance wars :

I can't figure out the algorithm to find the tiles where the unit can move, it also has to detect if there is an obstacle.

So it seems to me the algorithm has to do 2 things, first find all the tiles where the unit can go, and second find the shortest path between the unit and the cursor.

What would be a good way to implement this type of algorithm ?

Thanks.

##### Share on other sites

I've done this recently, although at a much granular level, but even for tiles, the concept remains largely the same.

Is your current ruleset only that movement is limited by a set amount of pts and that each move (no matter the direction) costs 1 point? (unless terrain is different).

##### Share on other sites

I can't figure out the algorithm to find the tiles where the unit can move, it also has to detect if there is an obstacle.
So it seems to me the algorithm has to do 2 things, first find all the tiles where the unit can go, and second find the shortest path between the unit and the cursor.

What would be a good way to implement this type of algorithm ?

You're looking for a graph algorithm. Here's an article: http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29

The trick here is being able to treat your map like a graph without actually trying to build a graph in memory. You can figure out things like edges and costs from your map data on the fly, and implement any graph algorithm that way.

To find the spaces and the paths, I would start out with Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

The wikipedia has a little animation of how the algorithm would act on a grid. I don't know if it really says anything about how to treat a typical 2D array as a graph. There are probably some concrete examples out there for 2D grids already.

I hope that's enough to get started.

##### Share on other sites

Is your current ruleset only that movement is limited by a set amount of pts and that each move (no matter the direction) costs 1 point? (unless terrain is different).

Set max movement points based on unit, with terrains using varied amounts depending on unit type (tread cost differs from tire cost when driving through woods, for example). Those are the Advance Wars rules.

##### Share on other sites

A* is the way

…for the last step of finding the shortest path.

L. Spiro

##### Share on other sites

A* is the way

…for the last step of finding the shortest path.

L. Spiro

Yes, but it is probably his real need I suppose.

For the sake of completeness I can suggest bresenham algorithm for the need of know what tiles are reachable/walkable (within a range), but is seems much more a "range spell/attack effect" need, or the classic field of view.

##### Share on other sites

Is your current ruleset only that movement is limited by a set amount of pts and that each move (no matter the direction) costs 1 point? (unless terrain is different).

Set max movement points based on unit, with terrains using varied amounts depending on unit type (tread cost differs from tire cost when driving through woods, for example). Those are the Advance Wars rules.

I am familiar with this ruleset, but as the OP mentionned making something similar to, I was wondering if 'facing' and turns had to be considered as well. It's much easier to forego orientation, obviously.

##### Share on other sites

Thanks for all the replies guys !

Is your current ruleset only that movement is limited by a set amount of pts and that each move (no matter the direction) costs 1 point? (unless terrain is different).

Set max movement points based on unit, with terrains using varied amounts depending on unit type (tread cost differs from tire cost when driving through woods, for example). Those are the Advance Wars rules.

I am familiar with this ruleset, but as the OP mentionned making something similar to, I was wondering if 'facing' and turns had to be considered as well. It's much easier to forego orientation, obviously.

'facing' and turns won't cost any 'points'. The movemen is limited by the terrain tiles (only this type of unit can go there etc) and by the presence of ennemy units. They can't superpose.

I can't figure out the algorithm to find the tiles where the unit can move, it also has to detect if there is an obstacle.
So it seems to me the algorithm has to do 2 things, first find all the tiles where the unit can go, and second find the shortest path between the unit and the cursor.

What would be a good way to implement this type of algorithm ?

You're looking for a graph algorithm. Here's an article: http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29

The trick here is being able to treat your map like a graph without actually trying to build a graph in memory. You can figure out things like edges and costs from your map data on the fly, and implement any graph algorithm that way.

To find the spaces and the paths, I would start out with Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

The wikipedia has a little animation of how the algorithm would act on a grid. I don't know if it really says anything about how to treat a typical 2D array as a graph. There are probably some concrete examples out there for 2D grids already.

I hope that's enough to get started.

I will look at it, thanks.

##### Share on other sites

'facing' and turns won't cost any 'points'. The movemen is limited by the terrain tiles (only this type of unit can go there etc) and by the presence of ennemy units. They can't superpose.

Is the map 'deformable'? (Can terrain cost be alter by player abilities or events?)

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5

• 13
• 13
• 11
• 10
• 13
• ### Forum Statistics

• Total Topics
632960
• Total Posts
3009481
• ### Who's Online (See full list)

There are no registered users currently online

×