Labyrinth dynamisch erstellen

[pixartist]

ich habe folgende methode zum dynamischen erstellen eines zufälligen Pfades ohne überschneidung auf meinem raster...

public function randomConnect(x1,y1,x2,y2, t)
    {
        var s1 = arr.getStein(x1,y1);
        var s2 = arr.getStein(x2,y2);
        var dbg = 0;
        while(s1 != s2 && dbg < 10000)
        {
            s1.setType(t);
            dbg++;
            var a = arr.getNeighboursOfType(s1,1);
            var hca:Array = new Array(4);
            for(var i = 0; i<a.length; i++)
            {
                hca[i] = arr.countNeighboursOfType(a[i],1);
            }
            trace(hca);
            //getting the highest value:
            var hc = 0;
            for(var i = 0; i<hca.length; i++)
            {
                if(hca[i] > hc)
                    hc = hca[i];
            }
            //breaking if it cant continue...
            if(hc<=0)
            {
                trace("error!");
                break;
            }
            //collecting fields with highest value:
            var hca2:Array = new Array();
            for(var i = 0; i<hca.length; i++)
            {
                if(hca[i] == hc)
                    hca2.push(i);
            }
            //randoming a field:
            var f = Math.floor(Math.random()*hca2.length);
            //trace(hca2.length);
            s1 = a[hca2[f]];
            trace(f);
            trace(hca2);
                
                
        }
            
                
    } 

nun endet das ganze aber zu 99% in einer sackgasse und erreicht nie den endpunkt. ich habe mir schon überlegt, dass ich vorher ein paar "zwischenziele" generiere und dann die "bewegung" immer zum zielpunkt hinsteuere. Nun weis ich aber nicht, wie ich eine scheinbar zufällige bewegung zu einem bestimmten punkt hin generiere, die aber nicht gezielt aussieht! also sozusagen eine gezielte zufälligkeit...

mir ist klar wie ich einen richtungsvektor erstelle und dann entlang des vektor markiere, aber das ganze soll ja zufällig sein!

hat da jmd. ne idee?
danke!

[PinkDragon]

Meine Idee wäre zusätzlich eine wegfindungsroutine einzubauen und immer wenn er ein weiteres Stück erstellt, prüft er erst, ob man von diesem Punkt überhaupt noch ans Ziel kommen kann und wenn nicht, wird ein anderer Punkt gewählt. So erkennst du frühzeitig Sackgassen. Auch solltest du die alten Punkte gespeichert lassen, denn falls von dem Stück aus kein Weg weiter führt, kannst du dann einen Punkt zurück gehen und von dort weiter rechnen.
Nur braucht es so relativ viel Rechenleistung...

[pixartist]

jau das wär ne idee...ich hatte mir auch folgendes überlegt. erst erstelle ich eine strecke vom start zum ziel...dann teile ich diese strecke in 2 strecken mit einem zufälligen mittleren punkt und dann wende ich diese funktion rekursiv auf die teilstücke an ^^

aber da hab ich wieder überschneidungen....

[pixartist]

k hab jetzt ne wegfindung gebaut ... aber leider leidet das ganze jetzt unter einer totalen verklumpung, vorallem wenn ich mehrere pfade einzeichnen lasse!!

import LArray;
class Lab
{
    private var arr:LArray;
    public function Lab (xs, ys)
    {
        arr = new LArray (xs, ys);
    }
    public function init (t)
    {
        arr.init (t);
    }
    public function setType (x, y, t)
    {
        arr.getStein (x, y).setType (t);
    }
    public function findNWLDist (s1:LStein, s2:LStein):LStein
    {
        var n = arr.getNeighbours (s1);
        var l:LStein = undefined;
        var ld = -1;
        for (var i = 0; i < n.length; i++)
        {
            var d = arr.getDistance (n[i], s2);
            if (ld == -1 || d < ld)
            {
                l = n[i];
                ld = d;
            }
        }
        return l;
    }
    public function findNWLDistbutnot (s1:LStein, s2:LStein, t:Array):LStein
    {
        var n = arr.getNeighbours (s1);
        var l:LStein = undefined;
        var ld = -1;
        for (var i = 0; i < n.length; i++)
        {
            var d = arr.getDistance (n[i], s2);
            if ((ld == -1 || d < ld))
            {
                var tt = true;
                for (var h = 0; h < t.length; h++)
                {
                    if (n[i].getType () == t[h])
                    {
                        tt = false;
                    }
                }
                if (tt == true)
                {
                    l = n[i];
                    ld = d;
                }
            }
        }
        return l;
    }
    [.......]
 
// WEGFINDUNGSalgorithmus!
//+++++++++++++++++++
    public function connectable (x1, y1, x2, y2)
    {
        var dbg = 0;
        var s1 = arr.getStein (x1, y1);
        var s2 = arr.getStein (x2, y2);
        var way = new Array ();
        way.push ([s1, s1.getType ()]);
        var currentpos = way.length - 1;
        s1.setType (2);
        while (s1 != s2 && dbg < 10000)
        {
            s1 = findNWLDistbutnot (s1, s2, [0, 2]);
            if (s1 != undefined)
            {
                way.push ([s1, s1.getType ()]);
                s1.setType (2);
                currentpos = way.length - 1;
                dbg++;
            }
            else
            {
                currentpos--;
                s1 = way[way.length - 2];
                if (currentpos < 0)
                {
                    for (var i = 0; i < way.length; i++)
                    {
                        way[i][0].setType (way[i][1]);
                    }
                    return false;
                }
            }
        }
        if (s1 == s2)
        {
            for (var i = 0; i < way.length; i++)
            {
                way[i][0].setType (way[i][1]);
            }
            return true;
        }
    }
// Zufälliger weg wird generiert
//+++++++++++++++++++
    public function randomConnect (x1, y1, x2, y2, t)
    {
        var s1 = arr.getStein (x1, y1);
        var s2 = arr.getStein (x2, y2);
        var dbg = 0;
        var way:Array = new Array();
        way.push(s1);
        while (s1 != s2 && dbg < 10000)
        {
            
            s1.setType (t);
            dbg++;
            var a = arr.getNeighboursOfType (s1, 1);
            var hcan:Array = new Array ();
            for (var i = 0; i < a.length; i++)
            {
                hcan[i] = arr.countNeighboursOfType (a[i], 1);
            }
            // remove neightbors that have no path to target...
            var hca:Array = new Array ();
            for (var i = 0; i < a.length; i++)
            {
//pathfinding for points(uhh that costs time!!)
                if(connectable(a[i].getX(),a[i].getY(),s2.getX(),s2.getY()))
                    hca[i] = hcan[i];
                else
                    hca[i] = 0;
            }
            //getting the highest value:
            var hc = 0;
            for (var i = 0; i < hca.length; i++)
            {
                if (hca[i] > hc)
                {
                    hc = hca[i];
                }
            }
            //breaking if it cant continue...
            if (hc <= 0)
            {
                trace ("error!");
                break;
            }
            //collecting fields with highest value:   
            var hca2:Array = new Array ();
            for (var i = 0; i < hca.length; i++)
            {
                if (hca[i] == hc)
                {
                    hca2.push (i);
                }
            }
            
            
            //randoming a field:
            var f = Math.floor (Math.random () * hca2.length);
            //trace(hca2.length);
            s1 = a[hca2[f]];
            way.push(s1);
        }
        for(var k = 0;k<way.length;k++)
        {
//hier lasse ich  dann zufällig zusätzliche pfade hinzufügen...
 
            if(Math.random() < 0.1)
            {
                randomConnect(way[k].getX(), way[k].getY(), Math.floor(Math.random()*arr.getDimensions()[0]), Math.floor(Math.random()*arr.getDimensions()[0]), t)
            }
        }
    }
} 

[PinkDragon]

Könntest mal ne Beispiels-swf anhängen? under "verklumpen mehrerer Wege" kann ich mir in diesem Zusammenhang relativ wenig vorstellen...

[pixartist]

mit verklumpung meinte ich, dass die linien sehr oft aneinander liegen und so grössere flächen bilden. habe das problem behoben, indem ich um die linien eine art "schutzmantel" gelegt habe, der auch nicht geschnitten werden darf

achtung die berechnung behinhaltet massenhaft rekursion und ist nochnicht optimiert...wenn ich zeit habe werde ich noch nen algorithmus programmieren, welcher das raster in errreichbarkeitsbereiche einteilt. das wird die wegfindung sehr viel schneller machen (hoffentlich)
wenn ihr "verlangsamungspopups" bekommt..einfach "nein" klicken...das ganze dauert ne weile