Grid based movement with a movement cost.

[Rhinoceros]

I've run into an issue where I have no idea what I'm doing, but I think it might require pathfinding.

I want to have characters move around a map, which is grid based, but only be able to move a certain amount per turn, based on terrain.

Like this:


So you can move to any of the blue spaces, but not past them. Note how it allows further movement on roads. You'd be able to move 4 squares entirely on roads on one turn, 3 squares on plains, 2 in forests, swamps, etc. and 1 square through mountains. I can figure out movement per turn, but not with a cost. The only way I thought I found, I figured out that it took the movement cost for all the squares, even ones you aren't moving through.

[Roland_Yonaba]

Oh, this sounds like an interesting problem.
Well, pathfinding can be a solution. Can't think of any better one outside using pathfinding, at the moment, but you can go with a simple Astar, with some slight changes on the top.
That sounds like a perfect candidate for Jumper, as it provides mechanims to solve the problem quite easily and neatly.
Before I start with a quite extensive explanation, would you please enlighten me on the following detail:

You have a grid with different types of terrain. Each type of terrain requires a different cost. So, when moving, a unit would tend to chose the path requiring less cost, isn't it ? Meaning that it would prefer paths involving tiles with a lesser cost.
Well, then, does each unit allowed to traversed all the possible types of terrain at the same time ? In other words, can a unit follow a path that goes along a road, then turn and traverse a forest ?
Or second case, does this unit bound to walk of a specific type of terrain of a single turn ? Of course, it could be allowed to walk on another type of terrain for the next turn, etc. ?

[Fyfff]

Ya, you should use weighted graph (your tile map) and one of the "shortest path problem" algorithms that solve your problem.

[kclanc]

I'm under the impression that what you are doing is selecting a position, and then asking the program: can my character travel to this point given that it has x movement points to spend? In that case, you need a weighted-graph shortest path algorithm.

My recommended solution is that, instead of computing the shortest path to a single destination, you should compute shortest paths from one source to all destinations within its range. i.e. "single source shortest path on a weighted graph".

The standard algorithm for this, given that different weights are associated with different positions, is Dijkstra's. Dijkstra's will need to examine the weights of squares within a large blob surrounding your character, rather than a slim path. The thing is, depending on how big your map is, and the maximum travelling distance of your characters, examining all these squares is unlikely to be a performance issue. I think that Dijkstra's is probably the appropriate choice. Unlike A-Star, you would only have to run it once, then you would store the results to answer subsequent queries, which would most likely be from the same source.
http://en.wikipedia.org/wiki/Dijkstra's_algorithm


A-Star finds shortest paths in a way that minimizes the number of examined squares. Unlike Dijsktra's, this search is performed with a target destination in mind. However, it relies on a heuristic; for any position, you need to be able to make an underestimate which places a lower bound on the shortest path from that position to the destination. A lot of game programmers use a broken version of A-Star where they make overestimates instead of underestimates. This does not necessarily find the shortest path, but it finds a good enough one. In your case, I think that you require a correct shortest path. So could an A-Star heuristic be created for your scenario? Yes. I'm going to assume you only allow movement in the cardinal directions, but this could be generalized if that isn't the case. Assuming 1 is the minimum weight of a terrain, the manhattan disance from a point to the destination would be a correct heuristic. It assumes that you can continuously make progress toward the destination, and each movement is onto a terrain with minimum weight; there cannot be a path to the destination whose cost is lower than this.
http://en.wikipedia.org/wiki/A*_search_algorithm

To understand how these algorithms work, it's necessary to understand the concept of mathematical induction. I learned about this from a book called "Mathematics: A Discrete Introduction" by Ed Scheinerman. I learned about Dijkstra's algorithm from Introduction to Algorithms by Cormen et. al. I learned about A* from a crusty old book called Artificial Intelligence by Patrick Henry Winston. You could probably learn about all of this stuff on the internet, but if you want to understand this stuff deeper, the former two sources might be worth looking into.

edit: Oh, I just noticed that Roland posted a link to jumper. I didn't know that jumper implements Dijkstra's and A*! You might want to use jumper. Then you wouldn't have to go through the trouble of implementing your own pathfinder.

[Roland_Yonaba]

Oh, I just noticed that Roland posted a link to jumper. I didn't know that jumper implements Dijkstra's and A*! You might want to use jumper. Then you wouldn't have to go through the trouble of implementing your own pathfinder.

It also has Jump Point Search, Breadth-First search, Depth First search, ThetAstar...
Though I'd like to point out one thing, the implementation of Dijkstra's algorithm featured in Jumper is not really the standard one.
It basically runs Astar without H-Cost (HCost = 0), which fallbacks to Dijkstra's behavior. Yeah, I chose the easy way.
Though, one thing I have in mind for the next iteration of this library is to add a full implementation of Dijkstra's algorithm. I also have one ready, fo reference, here. Might need some light work to make it more user-friendly, but that would do.

And oh, Kclanc, that post was very learningful.

[Rhinoceros]

You have a grid with different types of terrain. Each type of terrain requires a different cost. So, when moving, a unit would tend to chose the path requiring less cost, isn't it ? Meaning that it would prefer paths involving tiles with a lesser cost.

Yes, it would show all possible locations a player can get to within one turn. It would move, its turn would end. This means it would have to find all the locations that are: A) reachable and B) as far away from the starting point as possible, which would mean the lowest-costing paths.

The AI would prefer to move as close to the target as possible, as quickly as possible, which might moving through mountains rather than through a road, even though (strictly speaking) they would move faster on roads.

Well, then, does each unit allowed to traversed all the possible types of terrain at the same time ? In other words, can a unit follow a path that goes along a road, then turn and traverse a forest ?
Or second case, does this unit bound to walk of a specific type of terrain of a single turn ? Of course, it could be allowed to walk on another type of terrain for the next turn, etc. ?

The most they can move on roads is 4 per turn, assuming they're moving only on roads. so each road would cost 1 "point" of movement, while plains would only allow 3 squares per turn, effectively costing 1.33... points of movement. So if they were to walk on two road tiles, spending 2 movement points, they could either move two more tiles on roads (2 more points, total of 4.), or one more on plains (1.33 more points, total of 3.33). To move to a new square, you have to be able to pay the full movement cost. so you wouldn't be able to go one more plains square, because you'd end up at 4.66, when the maximum would be 4.

...

Well, I suppose I'll look into those, then. Hopefully, Jumper will be enough, but that's not an excuse to avoid learning about pathfinding!

I'll try to figure all this out tomorrow, I have to get to work soon.

[Roland_Yonaba]

Yes, it would show all possible locations a player can get to within one turn. It would move, its turn would end. This means it would have to find all the locations that are: A) reachable and B) as far away from the starting point as possible, which would mean the lowest-costing paths.
The AI would prefer to move as close to the target as possible, as quickly as possible, which might moving through mountains rather than through a road, even though (strictly speaking) they would move faster on roads.

The most they can move on roads is 4 per turn, assuming they're moving only on roads. so each road would cost 1 "point" of movement, while plains would only allow 3 squares per turn, effectively costing 1.33... points of movement. So if they were to walk on two road tiles, spending 2 movement points, they could either move two more tiles on roads (2 more points, total of 4.), or one more on plains (1.33 more points, total of 3.33). To move to a new square, you have to be able to pay the full movement cost. so you wouldn't be able to go one more plains square, because you'd end up at 4.66, when the maximum would be 4.

Okay, I tried to figure this out, and I just think the Great Kclanc's suggestion is the best way to go.
Actually, your game map is short. I counted 45x33 nodes. So performance (and blazing fast optimizations) are not needed, I believe.
What you want is pathfinding on a weighted grid, since movement in the same directions does not implies the same cost. Most of the time, in such cases, Astar is preferred over Dijkstra's because it will perform noticeably faster, and expand fewer nodes since it makes use of an heuristic to guide the search quickly towards the goal.

But actually, since your game is turn-based, the following occurs: you only have one unit pathfinding at the same time. This unit tends to move towards a fixed goal. And this goal is unlikely to change very often. Given those assumptions, you can precalculate a navigation map that will be used for later pathfinding queries. Potential fields (see video) would have been great for that, but since the grid is weighted, they won't work here. Dijkstra's algorithm stands perfectly because, given a single source, it will calculate the shortest possible distance from that source to every other single node in the map. So, if you select the goal as a source, and pass it to the algorithm, it will annotate all passable nodes with a distance property. Later on, you can use this to move from any location to that goal. Even if you have different units scattered on the map, as long as the goal assigned does not change, they can perfectly use this same navigation map to walk towards the goal. You will only need to recalculate everything if the goal changes (or if the different units are not assigned the same goal).

To make things a bit more clear, I tried to workout a simple example. I have feeded the algorithm with your map.

Code: Select all

-- local map = { .. snip ..}

-- Requiring external code
local D = require 'dijkstra'
local Handler = require 'handlers.gridmap_handler'

-- Initializing things
local Dijkstra = D(Handler)
Handler.init(map)

-- Process dijkstra from some location: tile(1,33) is the goal (located on the lower right corner)
local source = Handler.getNode(1,33)
Dijkstra:process(source)

-- Prints the navigation map
for y,row in ipairs(map) do
  for x, weight in ipairs(row) do
    local node = Handler.getNode(x,y)
    io.write(('%4s'):format(node.distance-source.distance))
  end
  io.write('\n')
end

Here is the result. inf (short for infinity) corresponds to the impassable nodes (value 8). Note that, when given any position on this map, to navigate to the goal (distance = 0), you just have to select as a next step the neighbouring cell that has a lower value than the one you are actually standing on.



Note that, here I assumed a taxicab movement (meaning that only orthogonal also called cardinal directions are allowed), thus a 4-way grid. That way, a good heuristic would be:

Code: Select all

function distance(nodeA, nodeB)
  -- costOfMove is the value of the node to be reached, nodeB
  local costOfMove = map[nodeB.y][nodeB.x] -- we can get it from the map
  local dx, dy = nodeA.x - nodeB.x, nodeA.y - nodeB.y
  return costOfMove * (math.abs(dx) + math.abs(dy))
end

This can be easily extending to 8-ways grids (allowing diagonal moves).
Also, from the same map, it becomes fairly straightforward to calculate all the possible moves, given a maximum stepping ability per turn for any unit. You will only need to recalculte this map if the given source changes.

If you are interested in the code, I can share it as a gist. Let me know.

In case you have many units which are assigned different goals, but are still moving turn-based, then you might to consider Astar (for instance, a player walking towards a goal, and some ennemies chasing the player), Dijkstra can still work, but you will have to handle multimaps. Or, reconsider using Astar. But, in my opinion, performance drops are unlikely to arise in both cases, since, as I have already mentionned, your game map is quite short.

Hope this helps.

[Rhinoceros]

I would definitely appreciate some code, or pseudocode, to help me get on the right track.

[Roland_Yonaba]

There you go: dijkstra-map.

This is a quick and incomplete example of how you can use dijkstra search algorithm to move entities. Feel free to play with the code.
I mostly have 50% of the code already written, so i basically reuse it and spent some time to shape things up and add some comments.
Some things are not perfect, but i wanted to get quick results, so i leave them for future work.
Hope this helps, and feel free to ask any question in case some things remains unclear.