Rhinoceros wrote:
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.
