• Advertisement
Sign in to follow this  

[C++/SFML] Find tiled possible movement

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

If you intended to correct an error in the post then please contact us.

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 :

 

ab6b8480b2.png

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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?)

Share this post


Link to post
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?)

 

Didn't think about it. Let's say no

Share this post


Link to post
Share on other sites

Then, assuming the possibilities of a said map are known, and that its size is limited, it may be interesting for performances' sake to build a matrix. That matrix would contain the amount of points required to move 'to' a tile, and its physical position within the matrix would identify whether it is adjacent to another tile or not.

If diagonal movement is permitted, a few 'tricks' would need to be employed, but it would still work essentially the same way.

That way, you could end up with an integer matrix only (0-3 for movement points for example, and 99 for impassable tiles).

 

This approach should minimize process time at the expanse of added disk space requirement. Depending on your end-platform, this may be desirable.

 

This, obviously, wouldn't work with deformable terrain however.

 

The problem with A*, as mentioned above, the is the sheer amount of processing involved. It is generally better as you'll still need to build it for AI pathfinding, but it is overkill for the purpose of establishing the base of 'where your unit can move'.

Edited by Orymus3

Share this post


Link to post
Share on other sites


The problem with A*, as mentioned above, the is the sheer amount of processing involved. It is generally better as you'll still need to build it for AI pathfinding, but it is overkill for the purpose of establishing the base of 'where your unit can move'.

 

It depends on the size of the map and/or the distance that units can move. That "sheer amount of processing" should easily be doable at least once per frame, if not thousands of times per frame, especially for a typical turn-based game where the movement distance is going to be in the neighborhood of 10 or maybe 20 spaces maximum. If your A* cannot handle that you're doing it wrong.

 

Someone in this situation should do the simplest thing first, which is probably going to be Dijkstra's algorithm. A* is an optimization for when you have a single destination, while the simpler Dijkstra's algorithm fans out equally, which is what you want to find all the tiles you can get to within a certain movement cost. Then the shortest path to every single one of them is stored already as part of figuring out which tiles you can reach, so you do not even need A*.

 

The trouble with the cache is it restricts your game unless you're smart about storing all the information you need. Some guys might swim, some might be good at climbing through mountains or forests, some might fly: there are different costs depending on who's moving. It's trivial to account for this if you don't try to reuse any work. You could build something that takes all of that into account and caches whatever you want, but your game might be fine without it.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement