astar_test 5

http://www.redblobgames.com/pathfinding/a-star/introduction.html

http://www.untoldentertainment.com/blog/2010/08/20/introduction-to-a-a-star-pathfinding-in-actionscript-3-as3-2/

http://egloos.zum.com/cozycoz/v/9748811

가로 세로 대각선 이동 제어 

astar_test_5.unitypackage

using UnityEngine;

using System.Collections;

using System.Collections.Generic;

using iso;

using System.Linq;

namespace iso

{

    public class Point

    {

        public float x;

        public float y;

        public Point(float x = 0, float y = 0)

        {

            this.x = x;

            this.y = y;

        }

        public Vector2 getVector2()

        {

            return new Vector2(this.x, this.y);

        }

    }

    public class Tile

    {

        public float F;

        public float G;

        public float H;

        public Point pivot;

        public Point center;

        public Point iso;

        public Tile parent;

        public GameObject gameobj;

    }

}

public class App : MonoBehaviour

{

    public int maxTileCol;

    public int maxTileRow;

    public int tileWidth;

    public int tileHeight;

    public GameObject prefabTile;

    [HideInInspector]

    public int halfTileWidth, halfTileHeight;

    private Tile[,] tileGrid;

private Tile startTile;

    private List<Tile> openList = new List<Tile>();

    private List<Tile> closeList = new List<Tile>();

private List<Tile> searchedList = new List<Tile>();

    private int[,] grid = {

                          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0}, 

                          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

                          };

    void Awake()

    {

        tileGrid = new Tile[maxTileCol, maxTileRow];

        halfTileWidth = tileWidth / 2;

        halfTileHeight = tileHeight / 2;

    }

    // Use this for initialization

    void Start()

    {

        CreateMap();

    }

    void CreateMap()

    {

        for (int i = 0; i < this.maxTileRow; i++)

        {

            for (int j = 0; j < this.maxTileCol; j++)

            {

                int screenX = (j - i) * halfTileWidth;

                int screenY = -(j + i) * halfTileHeight;

                var isoPoint = convert2dToIsoABS(new Point(screenX, screenY));

                GameObject go = (GameObject)GameObject.Instantiate(prefabTile, new Vector3(screenX, screenY, 0), Quaternion.identity);

                go.name = isoPoint.x + "," + isoPoint.y;

                Tile tile = new Tile();

                tile.gameobj = go;

                tile.pivot = new Point(screenX, screenY);

                tile.center = new Point(screenX, screenY - halfTileHeight);

                tile.iso = isoPoint;

                tileGrid[(int)isoPoint.x, (int)isoPoint.y] = tile;

                

                go.transform.FindChild("sprite/textmesh").GetComponent<TextMesh>().text = tile.iso.x + " , " + tile.iso.y;

                    // + " / " + tile.pivot.x + " , " + tile.pivot.y;// + "\n" + tile.center.x + " , " + tile.center.y;

                if (grid[j, i] != 0) { 

                    Debug.Log(string.Format("{0}, {1} 는 막혀있습니다.", i, j));

                    go.transform.FindChild("sprite").GetComponent<SpriteRenderer>().color = Color.red;

                }

            }

        }

    }

    public Point convertIsoTo2D(Point p)

    {

        Point point = new Point();

        point.x = (Mathf.Abs(p.x) - Mathf.Abs(p.y)) * halfTileWidth;

        point.y = (Mathf.Abs(p.x) + Mathf.Abs(p.y)) * halfTileHeight;

        return point;

    }

    public Point convert2dToIso(Point p)

    {

        Point point = new Point();

        point.x = (float)System.Math.Truncate((p.x / this.halfTileWidth + p.y / this.halfTileHeight) / 2);

        point.y = (float)System.Math.Truncate((p.y / this.halfTileHeight - (p.x / this.halfTileWidth)) / 2);

        return point;

    }

    public Point convert2dToIsoABS(Point p)

    {

        Point point = new Point();

        point.x = Mathf.Abs((float)System.Math.Truncate((p.x / this.halfTileWidth + p.y / this.halfTileHeight) / 2));

        point.y = Mathf.Abs((float)System.Math.Truncate((p.y / this.halfTileHeight - (p.x / this.halfTileWidth)) / 2));

        return point;

    }

    // Update is called once per frame

    

Point endPoint = new Point(9, 8);

    void Update()

    {

        

        if (Input.GetMouseButtonUp(0))

        {

// =========================== RELEASE ================================

StopAllCoroutines();

openList.Clear();

closeList.Clear();

searchedList.Clear();

// for (int i = 0; i < maxTileRow; i++) {

// for (int j = 0; j < maxTileCol; j++) { 

// if( grid [ i, j ] == 0)

// tileGrid[j, i].gameobj.transform.FindChild("sprite").GetComponent<SpriteRenderer>().color = Color.white;

// }

// }

// ===========================================================

for (int i = 0; i < maxTileRow; i++) {

for (int j = 0; j < maxTileCol; j++) { 

                    if( grid [ i, j ] == 0)

                        tileGrid[j, i].gameobj.transform.FindChild("sprite").GetComponent<SpriteRenderer>().color = Color.white;

                }

            }

            Vector3 pos = Camera.main.ScreenToWorldPoint(Input.mousePosition);

            Point p1 = convert2dToIsoABS(new Point(pos.x, pos.y));

            Point p2 = convertIsoTo2D(p1);

            int cx = (int)p2.x;

            if (pos.normalized.x > 0)

            {

                if (cx < 0) cx *= -1;

            }

            else

            {

                cx *= -1;

            }

            int cy = (int)(p2.y * -1);

            Point startPoint = new Point(cx, cy);

if( closeList.Count == 0 ){

startTile = tileGrid[ (int)p1.x, (int)p1.y ];

startTile.gameobj.transform.FindChild("sprite").GetComponent<SpriteRenderer>().color = Color.yellow;

}

tileGrid[(int)endPoint.x, (int)endPoint.y].gameobj.transform.FindChild("sprite").GetComponent<SpriteRenderer>().color = Color.yellow;

            //Debug.Log(string.Format("시작 지점: {0}, {1} => 도착 지점: {2}, {3}", p1.x, p1.y, endPoint.x, endPoint.y ));

            StartSearch(startPoint, endPoint);

        }

    }

    private void Trance() { 

        var strOpenList = "";

        var strCloseList = "";

        foreach (var tile in openList) { 

string strParent = (tile.parent == null) ? "parent is nul." : tile.parent.iso.x + " , " + 

tile.parent.iso.y;

            strOpenList += "(" + tile.iso.x + " , " + tile.iso.y + ") " +  strParent + "     ";

        }

        foreach (var tile in closeList) { 

string strParent = (tile.parent == null) ? "parent is null." : tile.parent.iso.x + " , " + 

tile.parent.iso.y;

            strCloseList += "(" + tile.iso.x + " , " + tile.iso.y + ") " + strParent + "     ";

        }

        Debug.Log("조사 안함 : " + strOpenList);

        Debug.Log("조사 함 : " + strCloseList);

    }

private Tile GetParent( Tile t) {

if (t.iso.x == startTile.iso.x && t.iso.y == startTile.iso.y) {

return null;

}

return t.parent;

}

    private void StartSearch(Point s, Point e)

    {

        var isoPoint = convert2dToIsoABS(new Point(s.x, s.y));

        var nextTile = tileGrid[ (int)isoPoint.x, (int)isoPoint.y ];

        if (!closeList.Contains(nextTile)) { 

            closeList.Add( nextTile );

        }

        

       

        //Debug.Log("시작 지점 : " + isoPoint.x + " , " + isoPoint.y);

Tile parentTile = tileGrid[(int)isoPoint.x, (int)isoPoint.y];

        validatePointAndAddList(parentTile, new Point(isoPoint.x - 1, isoPoint.y - 1), 64);

        validatePointAndAddList(parentTile, new Point(isoPoint.x - 1, isoPoint.y), 71.5f);

        validatePointAndAddList(parentTile, new Point(isoPoint.x - 1, isoPoint.y + 1), 128);

        validatePointAndAddList(parentTile, new Point(isoPoint.x, isoPoint.y + 1), 71.5f);

        validatePointAndAddList(parentTile, new Point(isoPoint.x + 1, isoPoint.y + 1), 64);

        validatePointAndAddList(parentTile, new Point(isoPoint.x + 1, isoPoint.y), 71.5f);

        validatePointAndAddList(parentTile, new Point(isoPoint.x + 1, isoPoint.y - 1), 128);

        validatePointAndAddList(parentTile, new Point(isoPoint.x, isoPoint.y - 1), 71.5f);

        //Trance();

        //--------------------------------- 조사 전 -----------------------------

        openList.Sort((a, b) => a.F.CompareTo(b.F));

        Tile searchedTile = openList.First();

        openList.Remove( searchedTile );

        if (!closeList.Contains(searchedTile)) { 

            closeList.Add( searchedTile );

        }

        

        Trance();

        int n = grid[(int)searchedTile.iso.y, (int)searchedTile.iso.x];

        if( n == 0 )

            tileGrid[(int)searchedTile.iso.x, (int)searchedTile.iso.y].gameobj.transform.FindChild("sprite").GetComponent<SpriteRenderer>().color = Color.green;

        if (searchedTile.iso.x == endPoint.x && searchedTile.iso.y == endPoint.y) { 

if( searchedTile.iso.x == endPoint.x && searchedTile.iso.y == endPoint.y ){

tileGrid[(int)searchedTile.iso.x, (int)searchedTile.iso.y].gameobj.transform.FindChild("sprite").GetComponent<SpriteRenderer>().color = Color.yellow;

}

            Debug.Log("<color=red> ***************** Search Finished... *****************</color>");

            var lastTile = closeList[ closeList.Count - 1 ];

Debug.Log("start tile's parent : " + closeList.First().parent);

Debug.Log("last tile's parent : " + closeList[closeList.Count-1].parent);

            

searchedList.Add(lastTile);

// recursive 

Tile parent = GetParent( lastTile );

string str = "";

while( parent != null ){

str += parent.iso.x + "," + parent.iso.y + " -> ";

searchedList.Add(parent);

parent = GetParent( parent );

}

searchedList.Reverse();

float duration = 0.1f;

foreach( Tile tile in searchedList) {

duration += 0.1f;

StartCoroutine( DelayDisplayResult( duration, tile ) );

}

// lastTile.parent;

// lastTile.parent.parent;

// lastTile.parent.parent.parent;

// lastTile.parent.parent.parent.parent;

//

//

// searchedList.Reverse();

// var strSearchedList = "";

// foreach( var tile in searchedList ){

// if( tile.iso.x == endPoint.x && tile.iso.y == endPoint.y )

// strSearchedList += tile.iso.x + " , " + tile.iso.y;

// else

// strSearchedList += tile.iso.x + " , " + tile.iso.y + " -> ";

// }

// Debug.Log (strSearchedList);

// DisplayResult();

        }

        else { 

            var screenPoint = convertIsoTo2D( searchedTile.iso );

            StartCoroutine( DelaySearch( 0.01f, screenPoint ) );

        }

        

    }

IEnumerator DelayDisplayResult(float t, Tile tile) { 

yield return new WaitForSeconds(t);

tileGrid[(int)tile.iso.x, (int)tile.iso.y].gameobj.transform.FindChild("sprite").GetComponent<SpriteRenderer>().color = Color.yellow;

}

    

    IEnumerator DelaySearch(float t, Point point) { 

        yield return new WaitForSeconds(t);

        StartSearch(point, endPoint);

    }

    private void validatePointAndAddList(Tile parentTile, Point p, float g)

    {

// Debug.Log (parentTile + " , " + p.x + " , " + p.y);

if (p.x == startTile.iso.x && p.y == startTile.iso.y)

parentTile = null;

        //Debug.Log( grid[ (int)p.x+1, (int)p.y] + " , " + grid[ (int)p.x, (int)p.y+1]);

        //Debug.Log( (int)(p.x-1) + " , " +  (int)p.y + " = " + grid[(int)(p.x-1) , (int)p.y] + " , " + "            /           " +

        //           (int)(p.x) + "  ,  " +  (int)(p.y+1) + " = " + grid[ (int)(p.x), (int)(p.y+1) ] );

        //// 

        // ;

try{

if( g == 128 && (grid[(int)p.y-1 , (int)p.x] != 0 && grid[(int)p.y, (int)p.x+1] != 0 ) ){

Debug.Log("can not move cross...");

return;

            }else if( g == 128 && (grid[(int)p.y, (int)(p.x-1)] != 0 && grid[ (int)(p.y+1) , (int)(p.x) ] != 0) ){

                //Debug.Log("<color=yellow> can not move cross... " + 

                //    (p.x-1) + " , " + p.y + " => " + grid[(int)(p.x-1), (int)p.y] + "   /   " + 

                //    (p.x) + " , " + (p.y+1) + " => " +  grid[ (int)(p.x), (int)(p.y+1) ]

                //    + "</color>");

                

                return;

            }

            

} catch( System.IndexOutOfRangeException e ){

}

// Debug.Log (p.x + " , " + (p.y -1 ) + " = " + grid [(int)p.y-1, (int)p.x] + " , " + grid[ 2, 5 ]);

if (p.x >= 0 && p.y >= 0 && p.y < maxTileRow && p.x < maxTileCol)

        {

            var tile = tileGrid[(int)p.x, (int)p.y];

            if (grid[(int)p.y, (int)p.x] == 0) { 

                

//

                if (tile.parent != null) { 

tile.G = g + tile.parent.G;        

                }

                else { 

                    tile.G = g;

                }

                var ep = convertIsoTo2D(endPoint);

                var sp = convertIsoTo2D(p);

                //Point screenPoint = convertIsoTo2D( p );

                //float dx = Mathf.Abs(sp.x - ep.x);

                //float dy = Mathf.Abs(sp.y - ep.y);

                float dx = Mathf.Abs(sp.x - ep.x);

                float dy = Mathf.Abs(sp.y - ep.y);

                //float h = Mathf.Sqrt(Mathf.Pow(dx,2) + Mathf.Pow(dy,2));

float h = 10 * (dx + dy);

                

                // Diagonal 

                //if( dx > dy ){

                //    h = 128 * dy + 64 *(dx-dy);

                //}

                //else { 

                //    h = 128 * dy + 64 *(dy-dx);

                //}

                

                // Manhattan 

                //h = dx + dy;

                tile.H = h;

                tile.F = g + h;

// tileGrid[(int)p.x, (int)p.y].gameobj.transform.FindChild("sprite/textmesh").GetComponent<TextMesh>().text 

//// = string.Format("{0}, {1}\nparent = {2}, {3}", p.x, p.y, tile.parent.iso.x.ToString() , tile.parent.iso.y.ToString());

// = string.Format("({0}, {1})\nh={2}", p.x, p.y, tile.G);

if( !closeList.Contains(tile) ){

if( !openList.Contains(tile) ){

// if ( ( crossx1 >= 0 && crossy1 >= 0 && crossy1 < maxTileRow && crossx1 < maxTileCol) || (crossx2 >= 0 && crossy2 >= 0 && crossy2 < maxTileRow && crossx2 < maxTileCol) ){

// return;

// }

if( parentTile != null ){

tile.parent = parentTile;

// tile.parent.iso.x = parentTile.iso.x;

// tile.parent.iso.y = parentTile.iso.y;

// tile.parent.iso.x = parentTile.iso.x;

// tile.parent.iso.y = parentTile.iso.y;

// tile.parent.F = parentTile.F;

// tile.parent.G = parentTile.G;

// tile.parent.H = parentTile.H;

// tile.parent.center = parentTile.center;

// tile.parent.gameobj = parentTile.gameobj;

tileGrid[(int)p.x, (int)p.y].gameobj.transform.FindChild("sprite/textmesh").GetComponent<TextMesh>().text 

= string.Format("({0}, {1})\ng={2}\nh={3}\nf={4}", p.x, p.y, 

               g, 

               tile.H,

               tile.F

               );

// = string.Format("{0}, {1}\nparent = {2}, {3}", p.x, p.y, tile.parent.iso.x.ToString() , tile.parent.iso.y.ToString());

// = string.Format("({0}, {1})\ng={2}\nh={3}\nf={4}\nparent={5},{6}", p.x, p.y, 

//                tile.G, 

//                tile.H,

//                tile.F,

//                tile.parent.iso.x, tile.parent.iso.y);

// = string.Format("({0}, {1})\nparent={2},{3}", p.x, p.y, 

//                tile.parent.iso.x, tile.parent.iso.y);

// = string.Format("({0}, {1})\nparent={2},{3}", p.x, p.y, 

//                parentTile.iso.x, parentTile.iso.y);

}

openList.Add( tile );

   

}

}

// if( !closeList.Contains( tile ) ){

// if (!openList.Contains(tile) ){

//

// openList.Add( tile );    

//// Debug.Log(string.Format("old: {0}, new: {1}", openList.Find( x=>x.gameobj.Equals(tile.gameobj)).F, tile.F));

//

// }else{

//

// }

// }

                

                //tempList.Add(tile);

                

            }

            else { 

                //Debug.Log(tile.iso.x + " , " + tile.iso.y + "는 막혀있습니다.");

            }

        }

        else

        {

            //Debug.Log(string.Format("<color=yellow>Invalid point : </color>{0}, {1}", p.x, p.y));

        }

    }

    private GameObject fieldGo;

    void OnGUI()

    {

    }

}