Jump to content
Unity Insider Forum
Sign in to follow this  
SyntaxTalkstoMe

A-Star Algorythmus

Recommended Posts

Guten Tag zusammen,

ich wollte mal nach eurer Meinung fragen, was diese Codezeilen angeht. Und zwar handelt es sich um einen AStar. Ich und ein Kumpel hatten bereits einen A-Star in Windows Forms programmiert, der auch funktioniert hatte. Nun versuchen wir das ganze aber nach Unity zu übertragen. 

Ich muss hervor heben, dass uns Bewusst ist, dass es dafür eigene Klassen gibt in Unity um eine Wegfindung einzubauen. Aber ich muss betonen, dass wir es bewusst anders machen wollten, gegen dass ja an sich nichts spricht.

Nun ist es so, dass es offenbar an Unity spezifischen Dingen scheitert. Logikfehler kann ich gegenwärtig auch noch nicht ausschließen. Aber vielleicht ist hier jemand bewandert in der Arbeitsweise eines A-Stars und kann uns einen Tipp geben woran es scheitert. 

1. Erster Fehler ist, dass er offenbar aus irgendeinen Grund evtl nur wenige Felder um sich überprüft und dann irgendwo stecken bleibt.

2.  Der wichtigste Fehler für mich wäre, warum das Monster dass den Spieler sucht, durch Wände durchgehen kann. Die Überprüfung sagt ja aus "Was wäre wenn dort eine Wand steht". Wir hatten verschiedene Dinge getestet. Bounds, Intersect, Contains. Die Wände sind Quads mit einem BoxCollider2D drauf.

3. Der Kollisionsdummy ist nur zu Testzwecken da.

 

 

Ich wäre euch sehr dankbar, wenn ihr zumindest Fehler 2 aufdecken könntet :)

 

using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using UnityEditor;
using UnityEngine;

public class AStar : MonoBehaviour
{

    public List<Node> openList = new List<Node>();
    public List<Node> closedList = new List<Node>();

    public GameObject player;
    public float speed = 0.5f;
    public float gridSize = 0.2f;

    public GameObject gelberPunkt;
    public GameObject punkt;

    GameObject[] wandListe;
    static List<GameObject> walls;
    Bounds[] bounds;

    Node aktuelleNode;
    Vector3 nextTarget;

    Rigidbody2D festkoerper;
    GameObject kollisionsDummy;


    void Start()
    {
        kollisionsDummy = new GameObject();
        kollisionsDummy.AddComponent<BoxCollider2D>();
        kollisionsDummy.GetComponent<BoxCollider2D>().size = gameObject.GetComponent<BoxCollider2D>().size;
        kollisionsDummy.transform.position = new Vector2(-999999, -999999);

        nextTarget = gameObject.transform.position;
        festkoerper = GetComponent<Rigidbody2D>();

        //Ermittelt die Bonds der Wandflächen
        if (wandListe == null)
        {
            wandListe = GameObject.FindGameObjectsWithTag("wand");
            bounds = new Bounds[wandListe.Length];
            for (int i = 0; i < wandListe.Length; i++)
            {
                bounds[i] = wandListe[i].GetComponent<Collider2D>().bounds;
            }
        }
    }

    private void Update()
    {
        if (Vector3.Distance(gameObject.transform.position, nextTarget) < 0.001f)
        {
            // print("Ich bin ins Pathfinding reingesprungen");
            Pathfinding();
        }
        //print("Gameobject posX " + gameObject.transform.position.x + "GameObject posY: " + gameObject.transform.position.y);
        //print("nextTarget posX " + nextTarget.x + "nextTarget posY: " + nextTarget.y);
        Vector3 richtung = (nextTarget - gameObject.transform.position);
        festkoerper.MovePosition(gameObject.transform.position + richtung.normalized * Time.deltaTime * speed);
    }

    public void Pathfinding()
    {
        openList.Clear();
        closedList.Clear();

        bool fertig = false;

        Node startNode = new Node(); // startpunkt
        startNode.letzteNode = null;
        startNode.posi = transform.position;
        startNode.laengeAktuelleNodeZumZiel = Vector3.Distance(player.transform.position, startNode.posi); // Geschätzte Länge Start <-> Ziel
        startNode.laengeAktuelleNodeZumStartPunkt = 0;
        startNode.gesamtWegLaenge = startNode.laengeAktuelleNodeZumStartPunkt + startNode.laengeAktuelleNodeZumZiel;

        closedList.Add(startNode);

        aktuelleNode = startNode;

        int end = 10;
        while (end > 0) // !fertig
        {
            List<Vector3> richtungsKoordinaten = new List<Vector3>();
            // Erstelle angrenzende Nodes und füge sie zur openList hinzu, falls noch
            // nicht in der openList enthalten und falls nicht von einem Collider blockiert

            richtungsKoordinaten.Add(aktuelleNode.posi + Vector3.up * gridSize); // Nord
            richtungsKoordinaten.Add(aktuelleNode.posi + (Vector3.up + Vector3.right) * gridSize); // Nordost
            richtungsKoordinaten.Add(aktuelleNode.posi + Vector3.right * gridSize); // Ost
            richtungsKoordinaten.Add(aktuelleNode.posi + (Vector3.down + Vector3.right) * gridSize); // Suedost
            richtungsKoordinaten.Add(aktuelleNode.posi + Vector3.down * gridSize); // Sued
            richtungsKoordinaten.Add(aktuelleNode.posi + (Vector3.down + Vector3.left) * gridSize); // SuedWest
            richtungsKoordinaten.Add(aktuelleNode.posi + Vector3.left * gridSize); // West
            richtungsKoordinaten.Add(aktuelleNode.posi + (Vector3.left + Vector3.up) * gridSize); // NordWest

            //Prüfe, ob sich die Positionen schon in der openList befinden

            //foreach (Node item in openList)
            //{
            //    print("OpenList Eintrag x: " + item.posi.x + " y: " + item.posi.y);
            //}

            foreach (Node item in openList)
            {
                for (int i = 0; i < richtungsKoordinaten.Count; i++)
                {
                    if (item.posi == richtungsKoordinaten[i])
                    {
                        richtungsKoordinaten.RemoveAt(i);
                        i--;
                       
                    }
                }
            }

            foreach (Node item in closedList)
            {
                for (int i = 0; i < richtungsKoordinaten.Count; i++)
                {
                    if (item.posi == richtungsKoordinaten[i])
                    {
                        richtungsKoordinaten.RemoveAt(i);
                        i--;
                    }
                }
            }

            for (int j = 0; j < richtungsKoordinaten.Count; j++)
            {           
                for (int i = 0; i < bounds.Length; i++)
                {
                    kollisionsDummy.transform.position = new Vector2(-0.8f, -1.3f); // richtungsKoordinaten[j];

                    print("Dummy Position: " + kollisionsDummy.transform.position);
                    print("Dumm Bounds Size: " + kollisionsDummy.GetComponent<BoxCollider2D>().bounds.size);
                        
                    if (bounds[i].Intersects(kollisionsDummy.GetComponent<BoxCollider2D>().bounds)) // kollisionsDummy.GetComponent<BoxCollider2D>().bounds
                    {
                        print("Kollision stattgefunden: " + richtungsKoordinaten[j]);
                        richtungsKoordinaten.RemoveAt(j);
                        j--;
                        break;

                    }
                }
            }

            //openList mit verfügbaren Nodes befüllen
            for (int i = 0; i < richtungsKoordinaten.Count; i++)
            {
                CreateNode(richtungsKoordinaten[i], aktuelleNode);
            }

            // Sortiere openList aufsteigend nach der Gesamtweglänge

            Node speicher;
            for (int j = openList.Count - 1; j > 0; j--)
            {
                for (int i = 0; i < j; i++)
                {
                    if (openList[i].gesamtWegLaenge > openList[i + 1].gesamtWegLaenge)
                    {
                        speicher = openList[i];
                        openList[i] = openList[i + 1];
                        openList[i + 1] = speicher;
                    }
                }
            }

            // Setze Node mit der kleinsten Gesamtweglänge aus der openList in die closedList

            if(openList.Count > 0)
            {
                closedList.Add(openList[0]);
                aktuelleNode = openList[0];
                openList.RemoveAt(0);
            }
            
            //foreach (Node item in openList)
            //{
            //    GameObject punktGelb = Instantiate(gelberPunkt);
            //    punktGelb.transform.position = item.posi;
            //}

            GameObject roterPunkt = Instantiate(punkt);
            roterPunkt.transform.position = aktuelleNode.posi;


            Vector3 playerStandort = player.transform.position;

            for (int i = 0; i < openList.Count; i++)
            {
                if ((Vector3.Distance(playerStandort, openList[i].posi) <= 0.001f))
                {
                    fertig = true;
                    Node naechsterWegpunkt = openList[i];

                    while (true)
                    {
                        if (naechsterWegpunkt.letzteNode == startNode)
                        {
                            break;
                        }
                        naechsterWegpunkt = naechsterWegpunkt.letzteNode;
                        print("naechsterWegpunkt wird befüllt");
                    }
                    nextTarget = naechsterWegpunkt.posi;
                }
            }
            end--;

            for (int i = 0; i < closedList.Count; i++)
            {
                print("Inhalt closed" + closedList[i]);
            }
        }
    }


    public void CreateNode(Vector3 pos, Node lastNode)
    {
        Node neueNode = new Node();
        neueNode.posi = pos;
        neueNode.letzteNode = lastNode;
        neueNode.laengeAktuelleNodeZumZiel = Vector3.Distance(player.transform.position, neueNode.posi);
        neueNode.laengeAktuelleNodeZumStartPunkt = neueNode.letzteNode.laengeAktuelleNodeZumStartPunkt + Vector3.Distance(neueNode.posi, neueNode.letzteNode.posi);
        neueNode.gesamtWegLaenge = neueNode.laengeAktuelleNodeZumZiel + neueNode.laengeAktuelleNodeZumStartPunkt;

        openList.Add(neueNode);
    }

    public class Node
    {
        public float laengeAktuelleNodeZumStartPunkt;
        public float laengeAktuelleNodeZumZiel;
        public Vector3 posi;
        public Node letzteNode;
        public float gesamtWegLaenge;
    }
}

 

Share this post


Link to post
Share on other sites

Wenn ihr den Algorithmus ordentlich programmiert hättet, könntet ihr den Core einfach 1:1 kopieren.

Das Grundproblem ist schon, dass der Algorithmus nix mit monobehavior zu tun hat, also bitte pack ihn in eine eigene Klasse. Spiel-Objekte sollten ihn nach einem Weg "fragen" und nicht implementieren.

Die "Knoten" sollten auch nur die Informationen haben, die der Algorithmus braucht und evtl als interface implementiert werden.

Außerdem sollten die Wegpunkte nicht von jedem Monster erstellt werden sondern als Struktur zentral (Singelton?) vorliegen. Bestenfalls vorgebacken.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×