Pathfinding help

I’ve created a fairly simple A* Pathfinding script, but I have encountered one problem. The pathfinder will try and take the shortest path, only to find that there’s a one node gap between it and the target node and it keeps doubling back on itself. So it’ll move up right next to the target node, but all the nodes leading around the pathfinder are all blocked (including the one in-between the pathfinder and the target node) and the only way out is the way it came. But as soon as it moves back the way it came, it tries to re-do what it just did, and then creates this loop where it just moves back & forth. I have no idea how to avoid this. What should I do?

Here’s some of the code if it’ll help you understand:

void CheckNode () {

		float lowestF = Mathf.Infinity;
		Transform nextNode = null;

		int a = 0;
		while(a < open.Count){
			List<Transform> thisOpen = FindAdjacentNodes(open[a]);
			bool addWeight = false;
			float weight = 0;
			foreach(Transform n in thisOpen){
				if(!open.Contains(n) && !addWeight){
					addWeight = false;
					weight = 0;
					addWeight = true;
					weight = errorWeight;
			if((((current.position - open[a].position).magnitude + (finish.position - open[a].position).magnitude) + weight) < lowestF){
				nextNode = open[a];
				lowestF = (current.position - open[a].position).magnitude + (finish.position - open[a].position).magnitude;

		current = nextNode;
		lastOpen = open;
		open = FindAdjacentNodes(current);
			int b = 0;
			while(b < nodes.Count){
				int c = 0;
				while(c < nodes**.nodeVectors.Count){**

** foreach(Transform n in lastOpen){**
__ if(n == nodes**.nodeVectors**__
current = start;
current.renderer.material = green;


So the above problem has been solved, but the pathfinding itself still gives me a weird path. I started this thread here if maybe you could help me out.


First of all, I would encourage you to look into theta-star pathing, as it’s not any more complicated than A*, is more efficient, etc. For your particular problem, it would be really nice to see more information, but I think I get the gist of the issue.

Okay, so basically you have two similar options for a solution to this:

  • Give your pathing system “lookahead” to pre-evaluate the next-node solution.
  • Give your system a “history” or move-buffer so that ‘mistakes’ won’t be repeated.

From experience, I’d say that the first solution is preferable. There are two general ways to achieve this:

  • Naive lookahead: basically, your lookahead can only return a bool “pathNotValid”. As you can guess, this will mean “if I move here, I’ll have to move back”. This is easy to evaluate, but relatively short on information.
  • Weighted lookahead: this method is a little more expensive, but returns much more information. Essentially, you buffer a full round of node evaluation for the prospective node you’re going to move to. The only real difference is that you can apply some insane weight to the node you’re currently on. This way, your algorithm can stay the same, because you’ll be evaluating on weight; you’re simply heavily-punishing backtracking.

To sum up, when you’re evaluating the possible next nodes, queue them up with the most-desirable first, then do a lookahead to evaluate the next move from that node. Pass into this lookahead method the id of your current node, so that you can heavily weight backtracking.

**EDIT: ** You are going to hate me for this, but I’ve done it before (not in Unity, sadly) and it is an amazing tool to have. What I would suggest is the following:

Tie the nodes to GameObjects which can be manually or procedurally placed in your scene.

Your goal is to be able to step through the pathfinding steps, and color the nodes each step to reflect their state in the algorithm (neighbor, current node, etc). This way you can create different scenarios in which to test your algorithm.

The more robust solution would be to indicate path weight visually. The two ways to do this would be to either float text above each node, or to use the color value of the material to denote weight (start at 255,255,255 then make the material darker and darker if it’s a heavy path).

It’s 3am, I hope this makes sense. If not, I’ll rewrite in the morning.