Pathfinding movable area on a grid with varying movement costs

Question

In my 2D grid turn based project, during his turn a player moves from tile to tile, and for each tile of a certain type that he walks onto, I deduct a certain amount of 'move points' from his 'turn move power'.

I want to highlight the area in which the selected character can move during the current turn. Problem is, everything I was able to find only explains different ways on how to calculate the shortest path between Points A and B.

My question is: is there no other way to accomplish this, other than to check every single tile of my map (or those in the vicinity), and highlight the ones to which the cheapest path costs less than the player currently has 'move power left', or is there some more popular/effective way to do this? My concern is, that if a player's 'turn move power' reaches higher numbers, I will be making my game calculate a hundred shortest path algorythms. Any ideas on how should I go about making the highlighting happen would also be appreciated. Thanks!

Right now the best candidate looks to be Dijkstra's algorythm, since my tiles would have a 'weight', but is that really the way to go?

Answer 1

@tetramess Depends on how you impemented your "terrain" and how you want movement to work, for example: is diagonal walking enabled or not? Let's say its a 2D grid of cubes. when considered diagonal movement, calculating your range of movement is extremally simple: its a square with side of (2*x)+1 cubes, where x is character range. But since you will (probably) implement movement from point A to B selected, you will have to use pathfinding algorithm anyway. There are A LOT of youtube tutorials, mostly with hex grid, which is even more complicated. Worry not about calculations :) you will be working on simple arrays using A* or Dijkstra, using pathfinding only when needed. As for highlighting desirable range of movement, my first thought was creating a circle/sphere collider around your character and highlighting tiles that are inside, but still using an algorithm on simple array could be faster, but probably unnoticeably. As for sample project you can check [this very old project][1] its well written and works even in unity 2017.3 but i still recommend you starting with some youtube tutorial. Happy coding! [1]: https://github.com/hakimio/KR/tree/master/Project/Assets/Scripts/Arena

Pathfinding movable area on a grid with varying movement costs

1 Reply

Follow this Question

Related Questions