# Constrained A* problem

I've got a little problem with an A* algorithm that I need to Constrained a little bit.

Basically : I use an A* to find the shortest path between 2 randomly placed room in 3D space, and then build a corridor between them. The problem I found is that sometimes it makes chimney like corridors that are not ideal, so I constrict the A* so that if the last movement was up or down, you go sideways.

Everything is fine, but in some corner cases, it fails to find a path (when there is obviously one).

Like here between the blue and red dot :

(i'm in unity btw, but i don't think it matters)

Here is the code of the actual A* (a bit long, and some redundency)

while(current != goal)
{
//add stair up / stair down
foreach(Node<GridUnit> test in current.Neighbors)
{
if(!test.Data.empty && test != goal) continue;
//bug at arrival;
if(test == goal && penul !=null)
{
Vector3 currentDiff = current.Data.bounds.center - test.Data.bounds.center;
if(!Mathf.Approximately(currentDiff.y,0))
{
//wanna drop on the last
if(!coplanar(test.Data.bounds.center,current.Data.bounds.center,current.Data.parentUnit.bounds.center,to.Data.bounds.center))
{
continue;
}
else
{
if(Mathf.Approximately(to.Data.bounds.center.x, current.Data.parentUnit.bounds.center.x) &&
Mathf.Approximately(to.Data.bounds.center.z, current.Data.parentUnit.bounds.center.z))
{
continue;
}
}
}
}
if(current.Data.parentUnit != null)
{
Vector3 previousDiff = current.Data.parentUnit.bounds.center - current.Data.bounds.center;
Vector3 currentDiff = current.Data.bounds.center - test.Data.bounds.center;

if(!Mathf.Approximately(previousDiff.y,0))
{
if(!Mathf.Approximately(currentDiff.y,0))
{
//you wanna drop now :
continue;
}
if(current.Data.parentUnit.parentUnit != null)
{
if(!coplanar(test.Data.bounds.center,current.Data.bounds.center,current.Data.parentUnit.bounds.center,current.Data.parentUnit.parentUnit.bounds.center))
{
continue;
}else
{
if(Mathf.Approximately(test.Data.bounds.center.x, current.Data.parentUnit.parentUnit.bounds.center.x) &&
Mathf.Approximately(test.Data.bounds.center.z, current.Data.parentUnit.parentUnit.bounds.center.z))
{
continue;
}
}
}
}

}
g = current.Data.g + HEURISTIC(current.Data,test.Data);
h = HEURISTIC(test.Data,goal.Data);
f = g + h;
if(open.Contains(test) || closed.Contains(test))
{
if(test.Data.f > f)
{
//found a shorter path going passing through that point
test.Data.f = f;
test.Data.g = g;
test.Data.h = h;
test.Data.parentUnit = current.Data;
}
}
else
{
//jamais rencontré
test.Data.f = f;
test.Data.h = h;
test.Data.g = g;
test.Data.parentUnit = current.Data;

}
}
if(open.Count == 0)
{
Debug.Log("nothingfound");
//nothing more to test no path found, stay to from;
List<GridUnit> r = new List<GridUnit>();
return r;
}

//sort open from small to biggest travel cost
open.Sort(delegate(Node<GridUnit> x, Node<GridUnit> y) {
return (int)(x.Data.f-y.Data.f);
});
//get the smallest travel cost node;
Node<GridUnit> smallest = open[0];
current = smallest;
open.RemoveAt(0);
}

//build the path going backward;
List<GridUnit> ret = new List<GridUnit>();

if(penul != null)
{
ret.Insert(0,to.Data);
}
GridUnit cur = goal.Data;
ret.Insert(0,cur);

do{
cur = cur.parentUnit;
ret.Insert(0,cur);
} while(cur != from.Data);

return ret;


You see at the start of the foreach i constrict the A* like i said.

If you have any insight it would be cool.

Thanks

• What do you mean by "it makes chimney like corridors" ? could you post a screenshot showing how it looks (when it is not great) and how you would like it to be. – tigrou May 31 '14 at 22:06
• here is a doodle of what i mean (side view) : i.imgur.com/ZVba5bG.png – Ragekit May 31 '14 at 22:19