3 replies to this topic

[menyo]

Hi,

I need a pathfinding system in my game but i'm not sure what to choose and how much things should be added to it to make it work without eating my CPU. What i want is a large map, at least 512*512 tiles and have many layers of this size on top of each other. The map can be altered heavily and there will be many (100+) entities that will need pathfinding on this map and between these layers. The pathfinding does not have to be very accurate as in cutting corners. So what path finding system should i be using here, or at least start out with.

I did tinker on an idea but i'm not if this would work at all. Let's say i put Major nodes on each 10th tile in the X and Y axis. Then when finding a path just use these nodes to get as close a possible to the target and put them in a list. Then look for straight lines 2 to 4 straight lines till they pass that node in one axis. Now do the same for the next node. If the path can not be reached it should try a more sophisticated algorithm, but note that a major node can be in a place the entity can never reach so it should probably make a closest reachable tile as it's target. When finally near the last node use something like A* to get the entity to it's destination.

I already can see problems with this used in complicated mazes, and while my maps can be like that they will mostly have large halls and rooms. I can also see the entity walk into some dead end and then needs to traverse back using an expensive algorithm so this is still very flawed but might be improved with some ideas.

[IADaveMark]

512x512 isn't very big. What do you mean by "layer of this size on top of each other"?

[menyo]

Well, at least 512*512. If i could make it work fast enough for 5K+*5K+ that would be awesome.

With layers i pretty much mean 512*512*Layers as in the Z level for the map. Sorry i was not clear on that.

Anyway, i am currently testing a regular A* algorithm without independent tile costs on a 100*100 map. And when i order like 6 entities to walk across that map simultaneously using this A* i experience a fps drop when calculating all of there paths. I need pathfinding for much more units (although not all simultaneously) on a much larger map like 512*512*128.

Since i'm not that experienced with A* or other pathfinding systems i might just have inefficient code.

class Astar
	{
		int startX;
		int startY;
		int endX;
		int endY;
		List<Node> openNodeList = new List<Node>();
		List<Node> closedNodeList = new List<Node>();
		public List<Node> Path { get; private set; }
		Node newNode;
	  
		/// <summary>
		/// A* Pathfinding.
		/// </summary>
		/// <param name="startX">The current location X axis</param>
		/// <param name="startY">The current location Y axis</param>
		/// <param name="endX">The destination X axis.</param>
		/// <param name="endY">The destination Y axis</param>
		/// <param name="map">The current map</param>
		public Astar(int startX, int startY, int endX, int endY, Tile[,] map)
		{
			this.startX = startX;
			this.startY = startY;
			this.endX = endX;
			this.endY = endY;
			Path = new List<Node>();
			Node currentNode = new Node(startX, startY, 0, 0);
			openNodeList.Add(currentNode);
			while (true)
			{
				int FCost = 999999999;
							 
				foreach (Node node in openNodeList)
				{
					if (node.F < FCost)
					{
						FCost = node.F;
						currentNode = node;
					}
				}
				closedNodeList.Add(currentNode);
				if (currentNode.locX == this.endX && currentNode.locY == this.endY)
				{
					break;
				}
				openNodeList.Remove(currentNode);
				AddAdjacent(currentNode, map);
			}
			//when path is found
			if ((currentNode.locX == this.endX && currentNode.locY == this.endY))
			{
				Path.Add(currentNode);
				Node next = currentNode;
			  
				while (true)
				{
					if (next.parentNode == null)
					{
						break;
					}
					else
					{
						next = next.parentNode;
						Path.Add(next);
					}
				}
				//reverse path
				Path.Reverse();
			}

		}
		/// <summary>
		/// Adds adjacent tiles to the open node list
		/// </summary>
		/// <param name="node">Node to check.</param>
		/// <param name="map">Map to parse.</param>
		private void AddAdjacent(Node node, Tile[,] map)
		{
			//check N
			newNode = new Node(node.locX, node.locY - 1, node, 10 + node.G, ManhattanHeuristic(node.locX, node.locY - 1, this.endX, this.endY));
			if (map[newNode.locX, newNode.locY].TileType == TileType.Floor)
			{
				if (!closedNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}
					) && !openNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}))
				{
					openNodeList.Add(newNode);
				}
			}
			//check S
			newNode = new Node(node.locX, node.locY + 1, node, 10 + node.G, ManhattanHeuristic(node.locX, node.locY + 1, this.endX, this.endY));
			if (map[newNode.locX, newNode.locY].TileType == TileType.Floor)
			{
				if (!closedNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}
					) && !openNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}))
				{
					openNodeList.Add(newNode);
				}
			}
			//check W
			newNode = new Node(node.locX - 1, node.locY, node, 10 + node.G, ManhattanHeuristic(node.locX - 1, node.locY, this.endX, this.endY));
			if (map[newNode.locX, newNode.locY].TileType == TileType.Floor)
			{
				if (!closedNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}
					) && !openNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}))
				{
					openNodeList.Add(newNode);
				}
			}
			//check E
			newNode = new Node(node.locX + 1, node.locY, node, 10 + node.G, ManhattanHeuristic(node.locX + 1, node.locY, this.endX, this.endY));
			if (map[newNode.locX, newNode.locY].TileType == TileType.Floor)
			{
				if (!closedNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}
					) && !openNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}))
				{
					openNodeList.Add(newNode);
				}
			}
			//check NW
			newNode = new Node(node.locX - 1, node.locY - 1, node, 14 + node.G, ManhattanHeuristic(node.locX - 1, node.locY - 1, this.endX, this.endY));
			if (map[newNode.locX, newNode.locY].TileType == TileType.Floor)
			{
				if (!closedNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}
					) && !openNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}))
				{
					openNodeList.Add(newNode);
				}
			}
			//check NE
			newNode = new Node(node.locX + 1, node.locY - 1, node, 14 + node.G, ManhattanHeuristic(node.locX + 1, node.locY - 1, this.endX, this.endY));
			if (map[newNode.locX, newNode.locY].TileType == TileType.Floor)
			{
				if (!closedNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}
					) && !openNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}))
				{
					openNodeList.Add(newNode);
				}
			}
			//check SE
			newNode = new Node(node.locX + 1, node.locY + 1, node, 14 + node.G, ManhattanHeuristic(node.locX + 1, node.locY + 1, this.endX, this.endY));
			if (map[newNode.locX, newNode.locY].TileType == TileType.Floor)
			{
				if (!closedNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}
					) && !openNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}))
				{
					openNodeList.Add(newNode);
				}
			}
			//check SW
			newNode = new Node(node.locX - 1, node.locY + 1, node, 14 + node.G, ManhattanHeuristic(node.locX - 1, node.locY + 1, this.endX, this.endY));
			if (map[newNode.locX, newNode.locY].TileType == TileType.Floor)
			{
				if (!closedNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}
					) && !openNodeList.Exists(
					delegate(Node n)
					{
						return (n.locX == newNode.locX && n.locY == newNode.locY);
					}))
				{
					openNodeList.Add(newNode);
				}
			}
		}
		/// <summary>
		/// The Manhatten heuristic counts total tiles to destination. X to go + Y to go.
		/// </summary>
		/// <param name="startX">Start point X axis</param>
		/// <param name="startY">Start point Y axis</param>
		/// <param name="destX">Destination X axis</param>
		/// <param name="destY">Destination Y axis</param>
		/// <returns>Returns total number of tiles as int</returns>
		private int ManhattanHeuristic(int thisX, int thisY, int destX, int destY)
		{
			int MH = Math.Abs(thisX - destX) + Math.Abs(thisY - destY);
			//Multiply by 10 to simulate a single move.
			MH = MH * 10;
			return MH;
		}


	}

And the node class:

class Node
	{
		//location of this node
		public int locX { get; private set; }
		public int locY { get; private set; }
	  
		//REFINE: this might be replaced by just 2 integers.
		public Node parentNode { get; private set; }
		//Tile cost
		public int G { get; private set; }
		//Total heuristic cost to move from this node to final node
		public int H { get; private set; }
		//G+H
		public int F { get; private set; }
		/// <summary>
		/// Instantiates a node with parent used for A* pathfinding. Finding the best path where position and destination is already known.
		/// </summary>
		/// <param name="locX">This nodes X location.</param>
		/// <param name="locY">This nodes Y location.</param>
		/// <param name="parX">The parent node X location.</param>
		/// <param name="parY">The parent node Y location.</param>
		/// <param name="G">Tile cost.</param>
		/// <param name="H">Total heuristic cost to move from this node to final node.</param>
		public Node(int locX, int locY, Node parentNode, int G, int H)
		{
			this.locX = locX;
			this.locY = locY;
			this.parentNode = parentNode;
			this.G = G;
			this.H = H;
			F = G + H;
		}
		/// <summary>
		/// Instantiates the FIRST node, that does not have a parent, used for A* pathfinding. Finding the best path where position and destination is already known.
		/// </summary>
		/// <param name="locX">This nodes X location.</param>
		/// <param name="locY">This nodes Y location.</param>
		/// <param name="parX">The parent node X location.</param>
		/// <param name="parY">The parent node Y location.</param>
		/// <param name="G">Tile cost.</param>
		/// <param name="H">Total heuristic cost to move from this node to final node.</param>
		public Node(int locX, int locY, int G, int H)
		{
			this.locX = locX;
			this.locY = locY;
		  
			this.G = G;
			this.H = H;
			F = G + H;
		}
	}

I call a entity.method in the main update loop on a key press and pass the new destination with it. In that method i instantiate a new A* object, store the found path in the entity instance and change the destination. in the entity.update i check destination != position and if so i move that entity step by step.

If you stumbled uppon this looking for an A* alghorithm, feel free to use this code since it should work perfectly on smaller distances and/or less entities. I'd love a PM if this worked out for you though .

[ssrun]

You might want to look in to Hierarchical Pathfinding A* (HPA*). Secondly, it is quicker to store the open list in a heap based priority queue as opposed to a linked list. Your algorithm is extremely slow because you're potentially looping through thousands of entries to find the lowest cost node. As you insert nodes into the open and closed list, you should flag the nodes as being in the list so that you never have to search. Another point to think about is that the costs and parent pointers for the nodes need to be cleared when the next AI entity begins it's A* search. A quick way to handle this is to use a static variable to give each A* request a unique id and then tag each node with the current search id when it's visited for the first time in that search instance.