Unit.MovementPoints = 5
Segment.Distance = 2
First.Segment.Position = (1, 0, 1)
In the end what worked for me was actually
Dijkstra's/BFS which searches nothing, there is no end point. You could extend this to create a
Flow Field if you backtrack each tile but it's not required for this use case. Code represents a general idea and an algorithm, it's from my project, so it won't work out of the box.
// PolytopialSegmentsStructure = it's my grid.
// Segment = tile.
// Segment.Id = I set it to be the index in cached array from 0 to n.
// This is my thingy to get cost of a tile, you can ignore this.
[SerializeField] private ExperimentalSegmentCostRelation _experimentalSegmentCostRelation;
public override Segment GetNeighbours(Segment segment, int maxCost)
int capacity = segment.PolytopialSegmentsStructure._RelativeBounds.size.x * segment.PolytopialSegmentsStructure._RelativeBounds.size.y * segment.PolytopialSegmentsStructure._RelativeBounds.size.z;
Queue<Segment> frontier = new Queue<Segment>(capacity: capacity);
Dictionary<int, float> cost = new Dictionary<int, float>(capacity: capacity)
[segment.Id] = 0.0f
while (frontier.Count > 0)
Segment current = frontier.Dequeue();
Segment neighbours = current.GetNeighbours();
for (int a = 0; a < neighbours.Length; a++)
Segment next = neighbours[a];
float newCost = cost[current.Id] + this._experimentalSegmentCostRelation.GetCost(next) + 1; // + this.Distance(current, neighbours[a]) // + 1 was to replace distance
if (newCost <= maxCost && (!cost.ContainsKey(next.Id) || newCost < cost[next.Id]))
cost[next.Id] = newCost;
// This is me getting all of the tiles/segments this way because each key is Id anyway.
// In your case you might need to store your visited tiles this way `Dictionary<int, Segment>` where `int` would be `Segment.Id`.
// Or some other way.
// But in my case I can just get these visited tiles this way.
Segment segments = new Segment[cost.Keys.Count];
int i = 0;
foreach (int segmentId in cost.Keys)
segments[i] = this._gridSegmentsCache[segmentId];
More Details (My thoughts and steps I took to discover that algorithm above works.)
For small maps Flow Field algorithm would work in some cases.
I am also looking for the same thing. What I understood is in case we have max steps to take to reach some point that Flood Fill and similar algorithms won't work. The reason - they don't take into account the calculation of number of steps taken to reach the point. So in the end we need the same algorithm that is going to calculate a shortest path to do the job of calculating all possible distances it can reach with this amount of
We could use concept of Flow Field to optimize memory footprint and only save number of moves that need to be taken from one point of map to another. But the issue with this approach is not memory, it's rather we would have to recalculate this field each time some change on a map changes the
movement cost of a tile. One tile can affect many paths that were calculated before, so it would only be efficient for maps that don't change their
movement cost of a tile.
What if you don't care about
movement points to reach some tile? - You can just as well do the
Flood Fill constrained by
distance to check if this tile is reachable at all. Or if you don't need to check if it's reachable - then for a grid and hex maps it's easy to just calculate the tiles from simple math like
Clamp((int)(localPos +- radius), 0, maxX); - then use this result to iterate through tiles to get the ones you need. (This is rough pseudo-code, just for example.)
But of course, if we take
CIV 5 as an example, imagine tile changing to mountains, enemy unit stepping on a tile, your other unit occupies that other tile, a building, an obstacle, a river, an ocean. If we take into account all of these variables I can assume that
Flow Field would be a lot slower than using
DFS or BFS?
Using DFS or BFS = not possible for weighted graphs. https://stackoverflow.com/questions/30409493/using-bfs-for-weighted-graphs
So our case like
CIV 5 wouldn't work.
If we have a case like
CIV 5 and our
5 movement points and we need to get all of the tiles that we can reach with those
5 movement points - then we need to use pathfinding algorithm that is going to be used to find path to a tile player chooses this
Unit to go to, otherwise the result of path a
Unit takes and tiles that
Unit can reach will be inconsistent.
In code: Select all tiles that are distanced at
movement points as if each tile cost was
1 or lower possible distance. Run
A* on each of those to get correct distances and to check if they are reachable.
I keep thinking that there is a more efficient approach, even when using
A*. I would love to hear any ideas to optimize this to not run
A* on every possible tile. I think @UnderscoreZero is closer to the most efficient and right approach, it might even be the one. I am just leaving all of the considerations that I have taken till this point.
I came to a conclusion that we just need to calculate a
Weighted Flow Field and stop adding neighbours when max number of movement points is reached.
Weighted Flow Field with distance limit and starting from position of a
(Feel free to correct me if I am wrong, I would be very thankful for finding a better approach or fixing a mistake.)