3
\$\begingroup\$

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 :

1

(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;
                open.Add(test);

            }
        }
        closed.Add (current);
        if(open.Count == 0)
        {
            Debug.Log("nothingfound");
            //nothing more to test no path found, stay to from;
            List<GridUnit> r = new List<GridUnit>();
            r.Add(from.Data);
            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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – tigrou May 31 '14 at 22:06
  • \$\begingroup\$ here is a doodle of what i mean (side view) : i.imgur.com/ZVba5bG.png \$\endgroup\$ – Ragekit May 31 '14 at 22:19
1
\$\begingroup\$

It might be useful to just weight against undesirable characteristics as part of the path's score. Your current approach means you can't pathfind through actual chimneys, for example.

What if, say, you used the longest single direction run as a tiny penalty against the cost? Say, one millionth times the actual run length. Your pathfinder will then do diagonal lines to minimize the length of the single longest run in a best path, but with paths under a half million cells in length it's guaranteed to never have incentive to deviate from an actual best path.

The key understanding here, in my opinion, is that there are many best paths of matching lengths, and if you can get A*'s heuristic to actually measure which paths are more desirable, it will find the one you want without any hoop jumping at all.

\$\endgroup\$
  • \$\begingroup\$ The longest single direction run ? How do you get that ? I'm not sur I understand correctly. And also : my pathfinder can't do diagonal lines, cells of the grid are linked on axis, not diagonals, so, would your solution work ? \$\endgroup\$ – Ragekit Jun 1 '14 at 14:44
  • \$\begingroup\$ Ok : update : i switched the "continue" into the constrain test by a weight i add to the heuristic, and it seems to work. I keep the question opened while running a few tests but I think it's good \$\endgroup\$ – Ragekit Jun 1 '14 at 16:02
  • \$\begingroup\$ hum, i've still got some corner case where it doesn't work (it find a path but there's still no possibility to build a stair, like a 2 cell chimney and stuff like that). What I dit is that I use the constrain functions as a way to add a pretty huge number to the heuristic (so that it puts the cell at the end of the sorted open list, but still considers it if there's nothing else). Problem is when there's obviously something else, it still considers an invalid movement as valid :( \$\endgroup\$ – Ragekit Jun 1 '14 at 18:16
  • 1
    \$\begingroup\$ Ok : solution was avoid those corner cases to ever happen :p So it's working fine now. Thanks ! \$\endgroup\$ – Ragekit Jun 1 '14 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.