I’ve been looking around and there are alot of solutions to my problem for A* but I can’t seem to adapt them to it works for my dijkstra. Basically I have a tile based movement game using Dijkstra pathfinding to work around obstacles. I’ve implemented diagonal 8 way movement between tiles, the problem I have is that means that there is diagonal movement through corners of obstacle objects which visually doesn’t look right in the game. What I would like is so I can still keep this 8 way movement in empty space, but have it so I’m not cutting around corners. Here are two segments of my script, the first being what allows my 8 way movement, and the second is the Dijkstra pathfinding.
for (int x = 0; x < mapSizeX; x++) {
for (int z = 0; z < mapSizeX; z++) {
if (x > 0) {
graph [x, z].neighbours.Add (graph [x - 1, z]);
if (z > 0)
graph [x, z].neighbours.Add (graph [x - 1, z - 1]);
if (z < mapSizeZ - 1)
graph [x, z].neighbours.Add (graph [x - 1, z + 1]);
}
if (x < mapSizeX - 1) {
graph [x, z].neighbours.Add (graph [x + 1, z]);
if (z > 0)
graph [x, z].neighbours.Add (graph [x + 1, z - 1]);
if (z < mapSizeZ - 1)
graph [x, z].neighbours.Add (graph [x + 1, z + 1]);
}
if(z > 0)
graph [x, z].neighbours.Add (graph [x, z - 1]);
if(z < mapSizeZ-1)
graph [x, z].neighbours.Add (graph [x, z + 1]);
}
}
}
public void GeneratePathTo(int x, int z) {
selectedUnit.GetComponent<Unit> ().currentPath = null;
if (UnitCanEnterTile (x, z) == false) {
return;
}
Dictionary<Node, float> dist = new Dictionary<Node, float> ();
Dictionary<Node, Node> prev = new Dictionary<Node, Node>();
List<Node> unvisited = new List<Node> ();
Node source = graph[
selectedUnit.GetComponent<Unit>().tileX,
selectedUnit.GetComponent<Unit>().tileZ
];
Node target = graph[
x,
z
];
dist[source] = 0;
prev[source] = null;
foreach(Node v in graph) {
if(v != source) {
dist [v] = Mathf.Infinity;
prev [v] = null;
}
unvisited.Add (v);
}
while(unvisited.Count > 0) {
Node u = null;
foreach (Node possibleU in unvisited) {
if (u == null || dist [possibleU] < dist [u]) {
u = possibleU;
}
}
if (u == target) {
break;
}
unvisited.Remove(u);
foreach(Node v in u.neighbours) {
float alt = dist [u] + CostToEnterTile (u.x, u.z, v.x, v.z);
if (alt < dist [v]) {
dist [v] = alt;
prev [v] = u;
}
}
}
if (prev [target] == null) {
return;
}
List<Node> currentPath = new List<Node> ();
Node curr = target;
while(curr != null) {
currentPath.Add (curr);
curr = prev[curr];
}
currentPath.Reverse ();
selectedUnit.GetComponent<Unit>().currentPath = currentPath;
}
Ok cool, I understand this. How would I translate this to my code? Also how would I define passable and “at” (which appears as an unexpected symbol error)?
That’s just pseudo-code to describe a solution - your graph array should provide passability info that you can check before adding the neighbor. The actual implementation is left as an exercise for the reader.
Ok this is what I’ve come up with, my ‘walkable’ bool checks for colliders which is true when no collider is found, so thats what I used for the passability check before adding the neighbor, however I am given an Array Index is out of range error, any suggestions for how this can be solved?
void GeneratePathfindingGraph() {
graph = new Node[mapSizeX, mapSizeZ];
Vector3 worldBottomLeft = gridPos - Vector3.right * gridWorldSize.x/2f - Vector3.forward * gridWorldSize.y/2f;
for (int x = 0; x < mapSizeX; x++) {
for (int z = 0; z < mapSizeZ; z++) {
worldPoint = worldBottomLeft + Vector3.right * (x * nodeDiameter + nodeRadius) + Vector3.forward * (z * nodeDiameter + nodeRadius);
walkable = !(Physics.CheckSphere (worldPoint, nodeRadius, unwalkableMask));
Collider[] hitColliders = Physics.OverlapSphere (worldPoint, nodeRadius, unwalkableMask);
foreach (var c in hitColliders) {
foo = c.ClosestPointOnBounds (worldPoint);
foooX = (int) foo.x;
foooZ = (int) foo.z;
tiles [foooX, foooZ] = 2;
}
graph [x, z] = new Node (walkable, worldPoint);
graph [x, z].x = x;
graph [x, z].z = z;
}
}
for (int x = 0; x < mapSizeX; x++) {
for (int z = 0; z < mapSizeX; z++) {
if (x > 0) {
graph [x, z].neighbours.Add (graph [x - 1, z]);
if (z > 0)
graph [x, z].neighbours.Add (graph [x - 1, z - 1]);
if (z < mapSizeZ - 1)
graph [x, z].neighbours.Add (graph [x - 1, z + 1]);
}
if (x < mapSizeX - 1) {
graph [x, z].neighbours.Add (graph [x + 1, z]);
if (graph[x, z + 1].walkable == true)
if (graph [x + 1, z].walkable == true)
if (z > 0)
graph [x, z].neighbours.Add (graph [x + 1, z - 1]);
if (z < mapSizeZ - 1)
graph [x, z].neighbours.Add (graph [x + 1, z + 1]);
}
if(z > 0)
graph [x, z].neighbours.Add (graph [x, z - 1]);
if(z < mapSizeZ-1)
graph [x, z].neighbours.Add (graph [x, z + 1]);
}
}
}