溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

C#?AStar尋路算法怎么使用

發(fā)布時(shí)間：2023-03-31 14:19:29 來源：億速云 閱讀：107 作者：iii 欄目：開發(fā)技術(shù)

這篇文章主要講解了“C# AStar尋路算法怎么使用”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C# AStar尋路算法怎么使用”吧！

    概述

    AStar算法是一種圖形搜索算法，常用于尋路。他是以廣度優(yōu)先搜索為基礎(chǔ)，集Dijkstra算法和最佳優(yōu)先(best fit)于一身的一種算法。

    示例1:4向

    C#?AStar尋路算法怎么使用

    示例2:8向

    C#?AStar尋路算法怎么使用

    思路

    C#?AStar尋路算法怎么使用

    遞歸的通過估值函數(shù)找到最佳路徑，估值函數(shù)與距離相關(guān)，也有可能與通過代價(jià)系數(shù)相關(guān)（例如平地系數(shù)為1，坡地系數(shù)為2），有三個(gè)參數(shù)：

    • G：起點(diǎn)點(diǎn)到當(dāng)前點(diǎn)的代價(jià)

    • H: 當(dāng)前點(diǎn)到終點(diǎn)的代價(jià)

    • F: F = G + H 與最佳路徑權(quán)重負(fù)相關(guān)的參數(shù)

    過程大概：

    C#?AStar尋路算法怎么使用

    代碼示例

    位置定義

    public struct Vec2
{
    public int x;
    public int y;

    public Vec2(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public static Vec2 Zero
    {
        get
        {
            return new Vec2(0, 0);
        }
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Vec2))
            return false;

        var o = (Vec2)obj;
        return x == o.x && y == o.y;
    }

    public override int GetHashCode()
    {
        return x.GetHashCode() + y.GetHashCode();
    }

    public static Vec2 operator +(Vec2 a, Vec2 b)
    {
        return new Vec2(a.x + b.x, a.y + b.y);
    }

    public static Vec2 operator *(Vec2 a, int n)
    {
        return new Vec2(a.x * n, a.y * n);
    }

    public static Vec2 operator *(int n, Vec2 a)
    {
        return new Vec2(a.x * n, a.y * n);
    }

    public static bool operator ==(Vec2 a, Vec2 b)
    {
        return a.x == b.x && a.y == b.y;
    }

    public static bool operator !=(Vec2 a, Vec2 b)
    {
        return !(a.x == b.x && a.y == b.y);
    }
}

    方向定義

    public enum EDir
{
    Up = 0,
    Down = 1,
    Left = 2,
    Right = 3,
    UpLeft = 4,
    UpRight = 5,
    DownLeft = 6,
    DownRight = 7,
}

public abstract class CheckDirPol
{
    abstract public Dictionary<EDir, Vec2> GetDir();
}

public class CheckDir4Pol : CheckDirPol
{
    private Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2>
    {
        {EDir.Up, new Vec2(0, 1) },
        {EDir.Down, new Vec2(0, -1) },
        {EDir.Left, new Vec2(-1, 0) },
        {EDir.Right, new Vec2(1, 0) },
    };
    override public Dictionary<EDir, Vec2> GetDir()
    {
        return dirDict;
    }
}

public class CheckDir8Pol : CheckDirPol
{
    private Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2>
    {
        {EDir.Up, new Vec2(0, 1) },
        {EDir.Down, new Vec2(0, -1) },
        {EDir.Left, new Vec2(-1, 0) },
        {EDir.Right, new Vec2(1, 0) },
        {EDir.UpLeft, new Vec2(-1, 1) },
        {EDir.UpRight, new Vec2(1, 1) },
        {EDir.DownLeft, new Vec2(-1, -1) },
        {EDir.DownRight, new Vec2(1, -1) },

    };
    override public Dictionary<EDir, Vec2> GetDir()
    {
        return dirDict;
    }
}

    運(yùn)用策略模式的技巧，以實(shí)現(xiàn)4向，8向搜索切換

    估值函數(shù)

    public abstract class EvaPol
{
	abstract public float Calc(Vec2 a, Vec2 b);
}

public class MANEvaPol : EvaPol
{
    override public float Calc(Vec2 a, Vec2 b)
    {
        return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
    }
}

    直接使用曼哈頓距離作為代價(jià)

    節(jié)點(diǎn)定義

    public class Node
{
    public int id;
    public Vec2 pos;
    public float g;
    public float h;
    public float f;
    public Vec2 prePos;
    public bool hasPrePos;

    public Node(Vec2 pos)
    {
        this.pos = pos;
    }

    public void SetPrePos(Vec2 pos)
    {
        prePos = pos;
        hasPrePos = true;
    }
}

    算法上下文定義

    Context context;
EvaPol disPol;
CheckDirPol checkDirPol;

public struct Context
{
    public Vec2 end;
    public Vec2 start;
    public Node[,] nodes;
    public List<Node> open;
    public List<Node> close;
    public int[,] map;
    public List<Vec2> result;
    public Vec2 size;
}

    尋路算法

    初始化

    public void Init(Vec2 start, Vec2 end, int[,] map)
{
	var x = map.GetLength(0);
	var y = map.GetLength(1);
	context = new Context()
	{
		start = start,
		end = end,
		open = new List<Node>(),
		close = new List<Node>(),
		map = map,
		result = new List<Vec2>(),
		size = new Vec2(x, y),
	};

	context.nodes = new Node[x, y];
	for (int i = 0; i < x; i++)
		for (int j = 0; j < x; j++)
			context.nodes[i, j] = new Node(new Vec2(i, j));

	disPol = new MANEvaPol();
	//checkDirPol = new CheckDir4Pol();
	checkDirPol = new CheckDir8Pol();
}

    獲取路徑

    public List<Vec2> GetResult()
{
	return context.result;
}

    尋路

    尋路入口

    public void FindPath()
{
	var s = context.start;
	var sn = context.nodes[s.x, s.y];
	sn.g = 0;
	sn.h = disPol.Calc(s, context.end);
	sn.f = sn.g + sn.h;
	context.open.Add(sn);

	FindArrangement(sn);
}

    遞歸函數(shù)

    void FindArrangement(Node node)
{
	context.close.Add(node);
	context.open.Remove(node);

	if (node.pos == context.end)
	{
		SetResult(node);
		return;
	}

	CheckRound(node);
	if (context.open.Count == 0)
		return;

	Node next = context.open[0];
	for (int i = 1; i < context.open.Count; i++)
		if (context.open[i].f < next.f)
			next = context.open[i];

	FindArrangement(next);
}

    檢查周圍節(jié)點(diǎn)

    void CheckRound(Node node)
{
	var dirDict = checkDirPol.GetDir();
	foreach (var pair in dirDict)
	{
		var dir = node.pos + pair.Value;

		if (IsBlock(dir))
			continue;
		var dn = context.nodes[dir.x, dir.y];

		if (context.close.Contains(dn))
			continue;

		if (context.open.Contains(dn))
			TryOverridePath(node, dn);
		else
		{
			dn.g = disPol.Calc(dn.pos, context.start);
			dn.h = disPol.Calc(dn.pos, context.end);
			dn.f = dn.g + dn.h;
			dn.SetPrePos(node.pos);
			context.open.Add(dn);
		}
	}
}

// 若是從鄰節(jié)點(diǎn)到該節(jié)點(diǎn)路徑更優(yōu)，則替換更新
void TryOverridePath(Node a, Node b)
{
	var g = a.g + disPol.Calc(a.pos, b.pos);
	if (g < b.g)
	{
		b.g = g;
		b.SetPrePos(a.pos);
	}
}

bool IsBlock(Vec2 pos)
{
	return !InMap(pos) || context.map[pos.x, pos.y] == 1;
}

bool InMap(Vec2 pos)
{
	var x = pos.x;
	var y = pos.y;
	var size = context.size;
	return x >= 0 && x < size.x && y >= 0 && y < size.y;
}

    生成路徑

    void SetResult(Node node)
{
	Queue<Node> q = new Queue<Node>();
	while(node.hasPrePos)
	{
		q.Enqueue(node);
		node = context.nodes[node.prePos.x, node.prePos.y];
	}
	while(q.Count > 0)
	{
		context.result.Add(q.Dequeue().pos);
	}
}

    完整代碼

    using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public struct Vec2
{
    public int x;
    public int y;

    public Vec2(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public static Vec2 Zero
    {
        get
        {
            return new Vec2(0, 0);
        }
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Vec2))
            return false;

        var o = (Vec2)obj;
        return x == o.x && y == o.y;
    }

    public override int GetHashCode()
    {
        return x.GetHashCode() + y.GetHashCode();
    }

    public static Vec2 operator +(Vec2 a, Vec2 b)
    {
        return new Vec2(a.x + b.x, a.y + b.y);
    }

    public static Vec2 operator *(Vec2 a, int n)
    {
        return new Vec2(a.x * n, a.y * n);
    }

    public static Vec2 operator *(int n, Vec2 a)
    {
        return new Vec2(a.x * n, a.y * n);
    }

    public static bool operator ==(Vec2 a, Vec2 b)
    {
        return a.x == b.x && a.y == b.y;
    }

    public static bool operator !=(Vec2 a, Vec2 b)
    {
        return !(a.x == b.x && a.y == b.y);
    }
}

public enum EDir
{
    Up = 0,
    Down = 1,
    Left = 2,
    Right = 3,
    UpLeft = 4,
    UpRight = 5,
    DownLeft = 6,
    DownRight = 7,
}

public class AstarFindPath
{
    public class Node
    {
        public int id;
        public Vec2 pos;
        public float g;
        public float h;
        public float f;
        public Vec2 prePos;
        public bool hasPrePos;

        public Node(Vec2 pos)
        {
            this.pos = pos;
        }

        public void SetPrePos(Vec2 pos)
        {
            prePos = pos;
            hasPrePos = true;
        }
    }

    public abstract class EvaPol
    {
        abstract public float Calc(Vec2 a, Vec2 b);
    }

    public class MANEvaPol : EvaPol
    {
        override public float Calc(Vec2 a, Vec2 b)
        {
            return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
        }
    }

    public abstract class CheckDirPol
    {
        abstract public Dictionary<EDir, Vec2> GetDir();
    }

    public class CheckDir4Pol : CheckDirPol
    {
        private Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2>
        {
            {EDir.Up, new Vec2(0, 1) },
            {EDir.Down, new Vec2(0, -1) },
            {EDir.Left, new Vec2(-1, 0) },
            {EDir.Right, new Vec2(1, 0) },
        };
        override public Dictionary<EDir, Vec2> GetDir()
        {
            return dirDict;
        }
    }

    public class CheckDir8Pol : CheckDirPol
    {
        private Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2>
        {
            {EDir.Up, new Vec2(0, 1) },
            {EDir.Down, new Vec2(0, -1) },
            {EDir.Left, new Vec2(-1, 0) },
            {EDir.Right, new Vec2(1, 0) },
            {EDir.UpLeft, new Vec2(-1, 1) },
            {EDir.UpRight, new Vec2(1, 1) },
            {EDir.DownLeft, new Vec2(-1, -1) },
            {EDir.DownRight, new Vec2(1, -1) },

        };
        override public Dictionary<EDir, Vec2> GetDir()
        {
            return dirDict;
        }
    }

    public struct Context
    {
        public Vec2 end;
        public Vec2 start;
        public Node[,] nodes;
        public List<Node> open;
        public List<Node> close;
        public int[,] map;
        public List<Vec2> result;
        public Vec2 size;
    }

    Context context;
    EvaPol disPol;
    CheckDirPol checkDirPol;

    public void Init(Vec2 start, Vec2 end, int[,] map)
    {
        var x = map.GetLength(0);
        var y = map.GetLength(1);
        context = new Context()
        {
            start = start,
            end = end,
            open = new List<Node>(),
            close = new List<Node>(),
            map = map,
            result = new List<Vec2>(),
            size = new Vec2(x, y),
        };
        
        context.nodes = new Node[x, y];
        for (int i = 0; i < x; i++)
            for (int j = 0; j < x; j++)
                context.nodes[i, j] = new Node(new Vec2(i, j));

        disPol = new MANEvaPol();
        //checkDirPol = new CheckDir4Pol();
        checkDirPol = new CheckDir8Pol();
    }

    public void FindPath()
    {
        var s = context.start;
        var sn = context.nodes[s.x, s.y];
        sn.g = 0;
        sn.h = disPol.Calc(s, context.end);
        sn.f = sn.g + sn.h;
        context.open.Add(sn);
        
        FindArrangement(sn);
    }

    public List<Vec2> GetResult()
    {
        return context.result;
    }

    void FindArrangement(Node node)
    {
        context.close.Add(node);
        context.open.Remove(node);

        if (node.pos == context.end)
        {
            SetResult(node);
            return;
        }

        CheckRound(node);
        if (context.open.Count == 0)
            return;

        Node next = context.open[0];
        for (int i = 1; i < context.open.Count; i++)
            if (context.open[i].f < next.f)
                next = context.open[i];
        
        FindArrangement(next);
    }

    void SetResult(Node node)
    {
        Queue<Node> q = new Queue<Node>();
        while(node.hasPrePos)
        {
            q.Enqueue(node);
            node = context.nodes[node.prePos.x, node.prePos.y];
        }
        while(q.Count > 0)
        {
            context.result.Add(q.Dequeue().pos);
        }
    }

    void CheckRound(Node node)
    {
        var dirDict = checkDirPol.GetDir();
        foreach (var pair in dirDict)
        {
            var dir = node.pos + pair.Value;

            if (IsBlock(dir))
                continue;
            var dn = context.nodes[dir.x, dir.y];

            if (context.close.Contains(dn))
                continue;

            if (context.open.Contains(dn))
                TryOverridePath(node, dn);
            else
            {
                dn.g = disPol.Calc(dn.pos, context.start);
                dn.h = disPol.Calc(dn.pos, context.end);
                dn.f = dn.g + dn.h;
                dn.SetPrePos(node.pos);
                context.open.Add(dn);
            }
        }
    }

    void TryOverridePath(Node a, Node b)
    {
        var g = a.g + disPol.Calc(a.pos, b.pos);
        if (g < b.g)
        {
            b.g = g;
            b.SetPrePos(a.pos);
        }
    }

    bool IsBlock(Vec2 pos)
    {
        return !InMap(pos) || context.map[pos.x, pos.y] == 1;
    }

    bool InMap(Vec2 pos)
    {
        var x = pos.x;
        var y = pos.y;
        var size = context.size;
        return x >= 0 && x < size.x && y >= 0 && y < size.y;
    }
}

    感謝各位的閱讀，以上就是“C# AStar尋路算法怎么使用”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對C# AStar尋路算法怎么使用這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

    向AI問一下細(xì)節(jié)

    免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

    AI
    助
    手