Need help modifying my A* on a (hex) grid that's mostly "obstacles", but the actor can jump over X tiles
Solved! See my own answer.
I'm creating an app in which there is a hex based map. It takes a certain amount of time to travel between hexes and I'm trying to implement a way to press on any valid hex and get the optimal path (If possible) from the players current position.
Here comes the tricky part, only a few of the hexes are valid travel locations, so I need my path finding to be able to skip over empty hexes. Depending on the players "reach" they are allowed to skip otherwise invalid spaces. So if the players reach was f ex. 3, they are allowed to move 1, 2, or 3 spaces in one "move", even if hexes in between are invalid (Empty), but they are not allowed to "stop" on invalid hexes.
Example:
So far, I've implemented an A* pathfinding script with the help of these references:
- https://www.redblobgames.com/grids/hexagons/
- https://www.redblobgames.com/pathfinding/a-star/introduction.html
- https://gist.github.com/keithcollins/307c3335308fea62db2731265ab44c06
But I'm not sure how to implement the "Skipping" or "Jumping" funcitonality I'm looking for. I've specifically avoided using "edge" cost, because it would require a lot of changes to my current implementation, and direction doesn't matter at all.
My version of the A* function in the third reference link:
public void AStarSearch(MapHex startHex, MapHex goalHex)
{
if (goalHex.empty)
{
Debug.Log("Goal empty.");
return;
}
SimplePriorityQueue<MapHex> frontier =
new SimplePriorityQueue<MapHex>();
frontier.Enqueue(startHex, 0);
cameFrom.Add(startHex, startHex);
costSoFar.Add(startHex, 0);
while (frontier.Count > 0)
{
MapHex current = frontier.Dequeue();
if (current.Equals(goalHex)) break;
foreach (MapHex neighbor in GetNeighbors(current))
{
float newCost = costSoFar[current] + 1;
if (!costSoFar.ContainsKey(neighbor) ||
newCost < costSoFar[neighbor])
{
if (costSoFar.ContainsKey(neighbor))
{
costSoFar.Remove(neighbor);
cameFrom.Remove(neighbor);
}
costSoFar.Add(neighbor, newCost);
cameFrom.Add(neighbor, current);
float priority = newCost +
HexHeuristicDistance(neighbor, goalHex);
frontier.Enqueue(neighbor, priority);
}
}
}
}
I just don't know how to expand the search past otherwise impassable hexes, or similar. I need the final output to be the shortest route to the end hex (If any is possible), to display the route, and the distance travelled. Any help appreciated :)
Edit: Okay as per Ruzihm's suggestion I'm trying to expand my "GetNeighbors" function to achieve my goal. To get all "neighbors" in range of the max speed, I'm trying to implement the code from the "Movement range" section of Red Blob Games's hexgrid guide: https://www.redblobgames.com/grids/hexagons/#range (Second code snip)
Converting from python is proving to be a challenge though and I seem to have created an inefficient monster that may or may not work:
public IEnumerable<MapHex> GetNeighbors(MapHex hex, int distanceOffset)
{
if (distanceOffset == 0)
{
foreach (Vector2 dir in oddQDirections)
{
MapHex next = allMapHexes.Find(item => item.coordinate == new Vector2(hex.coordinate.x + dir.x, hex.coordinate.y + dir.y));
if (next != null)
{
yield return next;
}
}
}
else
{
List<MapHex> neighbors = new List<MapHex>();
List<MapHex> closeHexesX = new List<MapHex>();
Vector3 hexCubeCoord = OddQToCube(hex.coordinate);
foreach (MapHex closeHex in allMapHexes.FindAll(item => !item.empty && -(distanceOffset + 1) <= -OddQToCube(item.coordinate).x && -OddQToCube(item.coordinate).x <= distanceOffset + 1))
{
closeHexesX.Add(closeHex);
}
foreach (MapHex closeHex in closeHexesX.FindAll(item => Mathf.Max(-(distanceOffset + 1), -OddQToCube(item.coordinate).x - (distanceOffset + 1)) <= -OddQToCube(item.coordinate).y && -OddQToCube(item.coordinate).x <= Mathf.Min((distanceOffset + 1), -OddQToCube(item.coordinate).x + (distanceOffset + 1))))
{
Vector3 cubeCoord = OddQToCube(closeHex.coordinate);
cubeCoord.z = -cubeCoord.x - cubeCoord.y;
neighbors.Add(closeHexesX.Find(item => item.coordinate == CubeToOddQ(hexCubeCoord + cubeCoord)));
}
}
}
Maybe I'm better off just running GetDistance for each hex and return those that have a distance <= to "reach"..?
Alright so I ended up solving my problem (Thanks to some pointers from Ruzihm that made me rethink my problem) by simply checking all valid hexes in range, for each pathfinding node. I'm not sure this is the fastest method, but I already have a list of valid hexes, so I don't have iterate through all the empty hexes each loop and it seems to be fast enough.
Here's the "GetNeighbours" code I ended up using each path finding loop:
public List<MapHex> GetNeighborsInRange(MapHex hex, int distance)
{
List<MapHex> neighbors = new List<MapHex>();
if (distance == 0)
{
foreach (Vector2 dir in oddQDirections)
{
MapHex next = allMapHexes.Find(item => item.coordinate == new Vector2(hex.coordinate.x + dir.x, hex.coordinate.y + dir.y));
if (next != null)
{
neighbors.Add(next);
}
}
}
else
{
foreach (MapHex closeHex in nonEmptyMapHexes)
{
if (HexHeuristicDistance(hex, closeHex) <= distance)
{
neighbors.Add(closeHex);
}
}
}
return neighbors;
}
Oh also, here's the method I use to convert my pathfinding data into useful data in the form of an object I call "Journey":
public Journey GetLatestPath()
{
if (cameFrom == null || cameFrom.Count == 0 || costSoFar == null || costSoFar.Count == 0)
{
//Trying to run this before running an A* search.
return null;
}
int pathTravelTime = 0;
List<MapHex> path = new List<MapHex>();
MapHex current = aStarLatestGoal;
while (!current.Equals(aStarLatestStart))
{
if (!cameFrom.ContainsKey(current))
{
//A* was unable to find a valid path.
return null;
}
path.Add(current);
current = cameFrom[current];
pathTravelTime += HexHeuristicDistance(current, path[path.Count - 1]);
}
path.Reverse();
return new Journey(path, aStarLatestStart, pathTravelTime);
}
If you are using a cube or axial hex grid, check out this question for a possible solution to "Get all in range": https://gamedev.stackexchange.com/questions/116035/finding-cells-within-range-on-hexagonal-grid?rq=1