精华内容
下载资源
问答
  • python模拟实现A*寻路算法
    2021-02-04 05:30:29

    一、简介

    两点之间寻找最短路径,要考虑到存在障碍物遮挡和斜线移动的情况。

    二、具体说明

    说明可以参考下面的链接,对A*算法实现的描述。

    三、具体实现

    1、实现功能

    15a93443ae4e68cfd14ee008f4664d87.png

    2、寻路具体流程

    033c720e63e1a030e5da41d4ff17bba3.png

    3、关于F值

    f = g + h

    g表示当前移动到下一个点的消耗,平移为1,斜移动为 sqrt((x1-x2)**2 +(y1-y2)**2);

    h表示当前移动到终点的消耗,不考虑斜移,不考虑障碍物

    具体原理请查看下面的参考链接。

    完整实现:

    # -*- coding: utf-8 -*-

    import os,sys,random,math

    #地图设置

    gameMapWidth = 10

    gameMapHeight = 10

    gameMap = []

    #地图障碍物

    obstacleCount = 5

    #块状态

    ITEM_STAT_NORMAL = 0 #空点

    ITEM_STAT_OBSTACLE = 1 #障碍物

    ITEM_STAT_START = 2 #起点

    ITEM_STAT_END = 3 #终点

    #起点和终点

    spNum = -1

    epNum = -1

    #每块的属性

    class Item:

    def __init__(self,x,y,status):

    self.x = x

    self.y = y

    self.status = status

    self.mf = -1

    self.mg = -1

    self.mh = -1

    self.mParent = None

    self.isPath = 0

    #初始化地图

    def initMap():

    for wc in xrange(gameMapWidth):

    for hc in xrange(gameMapHeight):

    gameMap.append(Item(wc,hc,ITEM_STAT_NORMAL))

    #插入障碍物

    for oc in xrange(obstacleCount):

    choose = random.randint(gameMapWidth,gameMapWidth*gameMapHeight - 1)

    gameMap[choose].status = ITEM_STAT_OBSTACLE

    global spNum

    global epNum

    #选取起点和终点

    while (spNum == -1):

    choose = random.randint(0,gameMapWidth*gameMapHeight - 1)

    if gameMap[choose].status == 0:

    spNum = choose

    gameMap[spNum].status = ITEM_STAT_START

    while (epNum == -1):

    choose = random.randint(0,gameMapWidth*gameMapHeight - 1)

    if gameMap[choose].status == 0:

    epNum = choose

    gameMap[epNum].status = ITEM_STAT_END

    #输出地图信息

    def printMap():

    for itemc in xrange(len(gameMap)):

    if gameMap[itemc].status == ITEM_STAT_START:

    print "START",

    elif gameMap[itemc].status == ITEM_STAT_END:

    print "END ",

    elif gameMap[itemc].isPath == 1:

    print "path ",

    else:

    print "%d " %(gameMap[itemc].status),

    if (itemc + 1) % gameMapHeight == 0:

    print "\n"

    #寻路

    def findPath():

    global spNum

    global epNum

    #开启列表

    openPointList = []

    #关闭列表

    closePointList = []

    #开启列表插入起始点

    openPointList.append(gameMap[spNum])

    while (len(openPointList) > 0):

    #寻找开启列表中最小预算值的点

    minFPoint = findPointWithMinF(openPointList)

    #从开启列表移除,添加到关闭列表

    openPointList.remove(minFPoint)

    closePointList.append(minFPoint)

    #找到当前点周围点

    surroundList = findSurroundPoint(minFPoint,closePointList)

    #开始寻路

    for sp in surroundList:

    #存在在开启列表,说明上一块查找时并不是最优路径,考虑此次移动是否是最优路径

    if sp in openPointList:

    newPathG = CalcG(sp, minFPoint) #计算新路径下的G值

    if newPathG < sp.mg:

    sp.mg = newPathG

    sp.mf = sp.mg + sp.mh

    sp.mParent = minFPoint

    else:

    sp.mParent = minFPoint #当前查找到点指向上一个节点

    CalcF(sp, gameMap[epNum])

    openPointList.append(sp)

    if gameMap[epNum] in openPointList:

    gameMap[epNum].mParent = minFPoint

    break

    curp = gameMap[epNum]

    while True:

    curp.isPath = 1

    curp = curp.mParent

    if curp == None:

    break

    print "\n"

    printMap()

    def CalcG(point, minp):

    return math.sqrt((point.x - point.mParent.x)**2 + (point.y - point.mParent.y)**2) + minp.mg

    #计算每个点的F值

    def CalcF(point,endp):

    h = abs(endp.x - point.x) + abs(endp.y - point.y)

    g = 0

    if point.mParent == None:

    g = 0

    else:

    g = point.mParent.mg + math.sqrt((point.x - point.mParent.x)**2 + (point.y - point.mParent.y)**2)

    point.mg = g

    point.mh = h

    point.mf = g + h

    return

    #不能是障碍块,不包含在关闭列表中

    def notObstacleAndClose(point,closePointList):

    if point not in closePointList and point.status != ITEM_STAT_OBSTACLE:

    return True

    return False

    #查找周围块

    def findSurroundPoint(point,closePointList):

    surroundList = []

    up = None

    down = None

    left = None

    right = None

    leftUp = None

    rightUp = None

    leftDown = None

    rightDown = None

    #上面的点存在

    if point.x > 0:

    up = gameMap[gameMapHeight*(point.x - 1) + point.y]

    if notObstacleAndClose(up,closePointList):

    surroundList.append(up)

    #下面的点存在

    if point.x < gameMapWidth - 1:

    down = gameMap[gameMapHeight*(point.x + 1)+ point.y]

    if notObstacleAndClose(down,closePointList):

    surroundList.append(down)

    #左边的点存在

    if point.y > 0:

    left = gameMap[gameMapHeight*(point.x) + point.y - 1]

    if notObstacleAndClose(left, closePointList):

    surroundList.append(left)

    #右边的点存在

    if point.y < gameMapHeight - 1:

    right = gameMap[gameMapHeight*(point.x) + point.y + 1]

    if notObstacleAndClose(right,closePointList):

    surroundList.append(right)

    #斜方向的点还需考虑对应正方向不是障碍物

    #左上角的点存在

    if point.x > 0 and point.y > 0:

    leftUp = gameMap[gameMapHeight*(point.x - 1) + point.y - 1]

    if notObstacleAndClose(leftUp,closePointList) and left.status != ITEM_STAT_OBSTACLE and up.status != ITEM_STAT_OBSTACLE:

    surroundList.append(leftUp)

    #右上角的点存在

    if point.x > 0 and point.y < gameMapHeight - 1:

    rightUp = gameMap[gameMapHeight*(point.x-1) + point.y + 1]

    if notObstacleAndClose(rightUp,closePointList) and right.status != ITEM_STAT_OBSTACLE and up.status != ITEM_STAT_OBSTACLE:

    surroundList.append(rightUp)

    #左下角的点存在

    if point.x < gameMapWidth - 1 and point.y > 0:

    leftDown = gameMap[gameMapHeight*(point.x+1) + point.y - 1]

    if notObstacleAndClose(leftDown,closePointList) and left.status != ITEM_STAT_OBSTACLE and down.status != ITEM_STAT_OBSTACLE:

    surroundList.append(leftDown)

    #右下角的点存在

    if point.x < gameMapWidth - 1 and point.y < gameMapHeight - 1:

    rightDown = gameMap[gameMapHeight*(point.x+1) + point.y + 1]

    if notObstacleAndClose(rightDown,closePointList) and right.status != ITEM_STAT_OBSTACLE and down.status != ITEM_STAT_OBSTACLE:

    surroundList.append(rightDown)

    return surroundList

    #查找list中最小的f值

    def findPointWithMinF(openPointList):

    f = 0xffffff

    temp = None

    for pc in openPointList:

    if pc.mf < f:

    temp = pc

    f = pc.mf

    return temp

    def main():

    initMap() ##初始化地图

    printMap() ##输出初始化地图信息

    findPath() ##查找最优路径

    #入口

    main()

    参考:

    https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/

    https://blog.csdn.net/qq_33747722/article/details/78436919

    更多相关内容
  • A星寻路算法简介

    2017-08-28 08:56:52
    A星寻路算法介绍 原文作者:moshuiqianliu 你是否在做一款游戏的时候想创造一些怪兽或者游戏主角,让它们移动到特定的位置,避开墙壁和障碍物呢? 如果是的话,请看这篇教程,我们会展示如何使用A星寻路算法来实现...

    A星寻路算法介绍

    原文作者:莫水千流  原文链接

    你是否在做一款游戏的时候想创造一些怪兽或者游戏主角,让它们移动到特定的位置,避开墙壁和障碍物呢?

    如果是的话,请看这篇教程,我们会展示如何使用A星寻路算法来实现它!

    在网上已经有很多篇关于A星寻路算法的文章,但是大部分都是提供给已经了解基本原理的高级开发者的。

    本篇教程将从最基本的原理讲起。我们会一步步讲解A星寻路算法,幷配有很多图解和例子。

    不管你使用的是什么编程语言或者操作平台,你会发现本篇教程很有帮助,因为它在非编程语言的层面上解释了算法的原理。稍后,会有一篇教程,展示如何在Cocos2D iPhone 游戏中实现A星算法。

    现在找下到达一杯咖啡因饮料和美味的零食的最短路径,开始吧!:]

     

    一只探路猫

     

    让我们想象一下,有一款游戏,游戏中一只猫想要找到获取骨头的路线。

    “为什么会有一只猫想要骨头?!”你可能会这么想。在本游戏中, 这是一只狡猾的猫,他想捡起骨头给狗,以防止被咬死!:]

    现在想像一下下图中的猫想找到到达骨头的最短路径:

    不幸的是,猫不能直接从它当前的位置走到骨头的位置,因为有面墙挡住了去路,而且它在游戏中不是一只幽灵猫!

    游戏中的猫同样懒惰,它总是想找到最短路径,这样当他回家看望它的女朋友时不会太累:-)

    但是我们如何编写一个算法计算出猫要选择的那条路径呢?A星算法拯救了我们!

     

    简化搜索区域

     

    寻路的第一步是简化成容易控制的搜索区域。

    怎么处理要根据游戏来决定了。例如,我们可以将搜索区域划分成像素点,但是这样的划分粒度对于我们这款基于方块的游戏来说太高了(没必要)。

    作为代替,我们使用方块(一个正方形)作为寻路算法的单元。其他的形状类型也是可能的(比如三角形或者六边形),但是正方形是最简单并且最适合我们需求的。

    像那样去划分,我们的搜索区域可以简单的用一个地图大小的二维数组去表示。所以如果是25*25方块大小的地图,我们的搜索区域将会是一个有625 个正方形的数组。如果我们把地图划分成像素点,搜索区域就是一个有640,000个正方形的数组了(一个方块是32*32像素)!

    现在让我们基于目前的区域,把区域划分成多个方块来代表搜索空间(在这个简单的例子中,7*6个方块 = 42 个方块):

     

    Open和Closed列表

     

    既然我们创建了一个简单的搜索区域,我们来讨论下A星算法的工作原理吧。

    除了懒惰之外,我们的猫没有好的记忆力,所以它需要两个列表:

    1. 一个记录下所有被考虑来寻找最短路径的方块(称为open 列表)
    2. 一个记录下不会再被考虑的方块(成为closed列表)

    猫首先在closed列表中添加当前位置(我们把这个开始点称为点 “A”)。然后,把所有与它当前位置相邻的可通行小方块添加到open列表中。

    下图是猫在某一位置时的情景(绿色代表open列表):

    现在猫需要判断在这些选项中,哪项才是最短路径,但是它要如何去选择呢?

    在A星寻路算法中,通过给每一个方块一个和值,该值被称为路径增量。让我们看下它的工作原理!

    路径增量

     

    我们将会给每个方块一个G+H 和值:

    • G是从开始点A到当前方块的移动量。所以从开始点A到相邻小方块的移动量为1,该值会随着离开始点越来越远而增大。
    • H是从当前方块到目标点(我们把它称为点B,代表骨头!)的移动量估算值。这个常被称为探视,因为我们不确定移动量是多少 – 仅仅是一个估算值。

    你也许会对“移动量”感兴趣。在游戏中,这个概念很简单 – 仅仅是方块的数量。

    然而,在游戏中你可以对这个值做调整。例如:

    • 如果你允许对角线移动,你可以针对对角线移动把移动量调得大一点。
    • 如果你有不同的地形,你可以将相应的移动量调整得大一点 – 例如针对一块沼泽,水,或者猫女海报:-)

    这就是大概的意思 – 现在让我们详细分析下如何计算出G和H值。

    关于G值

     

    G是从开始点A到达当前方块的移动量(在本游戏中是指方块的数目)。

    为了计算出G的值,我们需要从它的前继(上一个方块)获取,然后加1。所以,每个方块的G值代表了从点A到该方块所形成路径的总移动量。

    例如,下图展示了两条到达不同骨头的路径,每个方块都标有它的G值:

    关于H值

    H值是从当前方块到终点的移动量估算值(在本游戏中是指方块的数目)。

    移动量估算值离真实值越接近,最终的路径会更加精确。如果估算值停止作用,很可能生成出来的路径不会是最短的(但是它可能是接近的)。这个题目相对复杂,所以我们不会再本教程中讲解,但是我在教程的末尾提供了一个网络链接,对它做了很好的解释。

    为了让它更简单,我们将使用“曼哈顿距离方法”(也叫“曼哈顿长”或者“城市街区距离”),它只是计算出距离点B,剩下的水平和垂直的方块数量,略去了障碍物或者不同陆地类型的数量。

    例如,下图展示了使用“城市街区距离”,从不同的开始点到终点,去估算H的值(黑色字):

    A星算法

     

    既然你知道如何计算每个方块的和值(我们将它称为F,等于G+H),  我们来看下A星算法的原理。

    猫会重复以下步骤来找到最短路径:

    1. 将方块添加到open列表中,该列表有最小的和值。且将这个方块称为S吧。
    2. 将S从open列表移除,然后添加S到closed列表中。
    3. 对于与S相邻的每一块可通行的方块T:
      1. 如果T在closed列表中:不管它。
      2. 如果T不在open列表中:添加它然后计算出它的和值。
      3. 如果T已经在open列表中:当我们使用当前生成的路径到达那里时,检查F 和值是否更小。如果是,更新它的和值和它的前继。

    如果你对它的工作原理还有点疑惑,不用担心 – 我们会用例子一步步介绍它的原理!:]

    猫的路径

    让我们看下我们的懒猫到达骨头的行程例子。

    在下图中,我根据以下内容,列出了公式F = G + H 中的每项值:

    • F(方块的和值):左上角
    • G(从A点到方块的移动量):左下角
    • H(从方块到B点的估算移动量): 右下角

    同时,箭头指示了到达相应方块的移动方向。

    最后,在每一步中,红色方块表示closed列表,绿色方块表示open列表。

    好的,我们开始吧!

    第一步

    第一步,猫会确定相对于开始位置(点A)的相邻方块,计算出他们的F和值,然后把他们添加到open列表中:

    你会看到每个方块都列出了H值(有两个是6,一个是4)。我建议根据“城市街区距离”去计算方块的相关值,确保你理解了它的原理。

    同时注意F值(在左上角)是G(左下角)值和H(右下脚)值的和。
    第二步

    在第二步中,猫选择了F和值最小的方块,把它添加到closed列表中,然后检索它的相邻方块的相关数值。

    现在你将看到拥有最小增量的是F值为4的方块。猫尝试添加所有相邻的方块到open列表中(然后计算他们的和值),除了猫自身的方块不能添加以外(因为它已经被添加到了closed列表中)或者它是墙壁方块(因为它不能通行)。

    注意被添加到open列表的两个新方块,他们的G值都增加了1,因为他们现在离开始点有2个方块远了。你也许需要再计算下“城市街区距离”以确保你理解了每个新方块的H值。
    第三步

    再次,我们选择了有最小F和值(5)的方块,继续重复之前的步骤:

    现在,只有一个可能的方块被添加到open列表中了,因为已经有一个相邻的方块在close列表中,其他两个是墙壁方块。

    第四步

    现在我们遇到了一个有趣的情况。正如你之前看到的,有4个方块的F和值都为7 – 我们要怎么做呢?!

    有几种解决方法可以使用,但是最简单(快速)的方法是一直跟着最近被添加到open列表中的方块。现在继续沿着最近被添加的方块前进。

    这次有两个可通过的相邻方块了,我们还是像之前那样计算他们的和值。
    第五步

    接着我们选择了最小和值(7)的方块,继续重复之前的步骤:

    我们越来越接近终点了!

    第六步

    你现在训练有素了!我打赌你能够猜出下一步是下面这样子了:

    我们差不多到终点了,但是这次你看到有两条到达骨头的最短路径提供给我们选择:

    在我们的例子中,有两条最短路径:

    • 1-2-3-4-5-6
    • 1-2-3-4-5-7

    It doesn’t really matter which of these we choose, it comes down to the actual implementation in code.

    选择哪一条其实没关系,现在到了真正用代码实现的时候了。

    第七步

    让我们从其中一块方块,再重复一遍步骤吧:

    啊哈,骨头在open列表中了!
    第八步

    现在目标方块在open列表中了,算法会把它添加到closed列表中:

    然后,算法要做的所有事情就是返回,计算出最终的路径!

    一只有远见的猫

    在上面的例子中,我们看到当猫在寻找最短路径时,它经常选择更好的方块(那个在它的未来最短路径上的方块)- 好像它是一只有远见的猫!

    但是如果猫是盲目的,并且总是选择第一个添加到它的列表上的方块,会发生什么事情?

    下图展示了所有在寻找过程中会被使用到的方块。你会看到猫在尝试更多的方块,但是它仍然找到了最短路径(不是之前的那条,而是另一条等价的):

    图中的红色方块不代表最短路径,它们只是代表在某个时候被选择为“S”的方块。

    我建议你看着上面的图,并且尝试过一遍步骤。这次无论你看到哪个相邻的方块,都选择“最坏”的方式去走。你会发现最后还是找到了最短路径!

    所以你可以看到跟随一个“错误的”方块是没有问题的,你仍然会在多次重复尝试后找到最短路径。

    所以在我们的实现中,我们会按照以下的算法添加方块到open列表中:

    • 相邻的方块会返回这些顺序: 上面/左边/下面/右边。
    • 当所有的方块都有相同的和值后,方块会被添加到open列表中(所以第一个被添加的方块是第一个被猫挑选的)。

    下面是从原路返回的示意图:

    最短的路径是从终点开始,一步步返回到起点构成的(例子:在终点我们可以看到箭头指向右边,所以该方块的前继在它的左边)。

    总的来说,我们可以用下面的伪代码,合成猫的寻找过程。这是Objective-C写的,但是你可以用任何的语言去实现它:

    [openList add:originalSquare]; // start by adding the original position to the open list
    do {
    	currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score
     
    	[closedList add:currentSquare]; // add the current square to the closed list
    	[openList remove:currentSquare]; // remove it to the open list
     
    	if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path
    		// PATH FOUND
    		break; // break the loop
    	}
     
    	adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares
     
    	foreach (aSquare in adjacentSquares) {
     
    		if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it
    			continue; // Go to the next adjacent square
    		}
     
    		if (![openList contains:aSquare]) { // if its not in the open list
     
    			// compute its score, set the parent
    			[openList add:aSquare]; // and add it to the open list
     
    		} else { // if its already in the open list
     
    			// test if using the current G score make the aSquare F score lower, if yes update the parent because it means its a better path
     
    		}
    	}
     
    } while(![openList isEmpty]); // Continue until there is no more available square in the open list (which means there is no path)


     

    展开全文
  • Unity学习日志_寻路系统简介 基础寻路系统(Unity自带的)需要先将地形设置为静态后才可以进行网格烘焙。 Navigation视图: 1. Object: Scene Filter:选择要进行烘焙的物体类型。All(可以烘焙所有物体),Mesh ...

    Unity学习日志_寻路系统简介

    基础寻路系统(Unity自带的)需要先将地形设置为静态后才可以进行网格烘焙。

    Navigation视图:

    1. Object:

    在这里插入图片描述

    1. Scene Filter:选择要进行烘焙的物体类型。All(可以烘焙所有物体),Mesh Renderers(只可以烘焙带有Renderer的物体),Terrains(只可以烘焙地形)。
    2. Navagation Static:上面为当前选中物体的名字,此项为设置此物体为导航静态(可烘焙)
    3. Generate OffMeshLinks:当勾选此属性后,此物体可以在Bake中使用对应的属性:Drop Height,Jump Distance。
    4. Navigation Area:当前物体烘焙后所在的Area。

    2. Bake:

    在这里插入图片描述

    1. Baked Agent Size下面:这里是一个展示模板,可以看到下面的属性调整结果。
    2. Agent Radius:烘焙代理的半径预设值,在unity寻路系统中,物体寻路依靠代理组件实现。该预设值直接决定了多宽的代理组件可以通过。
    3. Agent Height:烘焙代理高度预设值。该预设值直接决定了多高的代理组件可以通过。
      1. 注:这里设置的代理信息为一个场景的烘焙值,就好比造桥时需要预先规定一个桥宽和承重。代理组件的信息设置在Agents面板中。
    4. Max Slope:代理可迈上的最大坡度。
    5. Step Height:代理可迈上台阶的最高高度。
    6. Drop Height:下落高度。
    7. Jump Distance:跳跃距离。
      1. 注:此两项需要勾选Generate OffMeshLinks才会生效。
    8. Advanced:
      1. Manual Voxel Size:勾选后将可以手动输入体素值大小。
      2. Voxel Size:输入体素值,注:将体素值减半将使内存使用量扩大4倍,烘焙时间延长4倍。
      3. Min Region Area:网格面积小于此数值的地方将不生成网格。
      4. Height Mesh:勾选此项将保存网格的高度信息,当然,需要额外的性能和存储空间。

    3. Areas:

    此界面可以自定义烘焙Area。Cost为此烘焙物体的花费权重。

    在这里插入图片描述

    AreaMask值的设置:AreaMask值采用按位计算,第一层二进制为1,第二层二进制为10,第三层二进制为100。其中0代表Nothing,-1代表Everything。

    4. Agents:

    此面板属性实际确定代理类型。

    在这里插入图片描述

    Nav Mesh Agent:

    实际绑定在寻路物体上的代理组件。
    在这里插入图片描述

    属性:

    1. Agent Type:代理类型,来源于Navigation中的Agents面板。
    2. Base Offset:基础偏移,指的是代理边界与游戏物体本身的偏移量。
    3. Speed:寻路速度。
    4. Angular Speed:角速度。
    5. Acceleration:加速度。
    6. Stopping Distance:寻路到达目的地后与目的地坐标的距离。
    7. Auto Braking:自动制动。
    8. Obstacle Avoidance:障碍回避。可以处理当多个代理走同一条路的策略。
    9. Radius:代理半径。
    10. Height:代理高度。
    11. Quality:代理躲避质量。
    12. Priority:代理优先级,优先级低的代理会给优先级高的物体”让路“。
    13. Auto Traverse Off Mesh Link:是否自动通过off mesh Link。
    14. Auto Repath:当原有路线失效后是否重新计算路线。
    15. Area Mask:当前代理可以寻路的层。
      1. AreaMask值的设置:AreaMask值采用按位计算,第一层二进制为1,第二层二进制为10,第三层二进制为100。其中0代表Nothing,-1代表Everything。

    Off Mesh link:

    由于基础组件中烘焙的offweshlink只可以下降,不能上升(想要上升就需要提升代理的Step height),所以有了这个组件

    在这里插入图片描述

    属性:

    1. Start:起始点。
    2. End:终点。
    3. Cost Override:花费重写值,如果为正则此条路的花费变为该值,如果为负,则使用默认的花费。
    4. Bi Directional:是否双向。
    5. Activated:是否激活该条路线。
    6. Auto Update Position:是否自动更新位置,
    7. Navigation Area:此条路所在area层。

    Nav Mesh Obstacle:

    unity基础寻路系统中可以实现动态烘焙的组件。

    在这里插入图片描述

    属性:

    1. Shape:障碍物几何形状,分为方块和胶囊体。
    2. Center:Shape的中心点坐标。
    3. Size:Shape的大小。
    4. Carve:是否在网格中打孔,打孔之后将视为障碍物,而不再是一个代理。
      1. Move Threshold:移动阈值,障碍物移动多少距离后会重新打孔。
      2. Time To Stationary:障碍物多久不动会被认为是静止的。
      3. Carve Only Stationary:是否只在静止时在导航网络打孔。

    寻路系统的拓展新功能(需要单独下载):

    unity官方更新的寻路组件烘焙时不需要将物体设置为静态。

    Nav Mesh Surface:

    在这里插入图片描述

    实现的新特征:

    1. 多代理网格烘焙:

    为一个物体添加多个不同的surface组件,不同surface可以同时烘焙。

    2. 可实现垂直网格烘焙:

    基础寻路系统中无法烘焙一个延Y轴旋转90度的Plane,但新组件可以。

    3. 脚本控制网格烘焙:

    可以通过脚本对一片区域进行实时烘焙,但正常使用时实时烘焙往往采用Local Nav Mesh Builder + Nav Mesh Source Tag的形式。

    关于使用脚本控制网格烘焙时如何获取AgentTypeID:

    1. 使用NavMesh中的GetSettingsByIndex(返回值为NavMeshBuildSetting类型)来获得Navigation视图Agents面板中的某个特定的Agent。
    2. NavMeshBuildSetting中的AgentTypeID可以直接使用。
    private NavMeshSurface _navMeshSurface;
    
        private void Start()
        {
            //创建一个surface脚本
            _navMeshSurface = gameObject.AddComponent<NavMeshSurface>();
            //获取想要的AgentID
            NavMeshBuildSettings _settings = NavMesh.GetSettingsByIndex(1);
            //将AgentID赋值给surface中的agentTypeID
            _navMeshSurface.agentTypeID = _settings.agentTypeID;
        }
    

    属性:

    1. Agent Type:代理类型。
    2. Collect Objects:烘焙范围:有All(所有),Volume(Volume体积区域内),Children(子对象)。
    3. Include Layers:烘焙所包含的层。
    4. Use Geometry:烘焙带有XXX的物体,有Render Meshes(烘焙带有Mesh Renderer的物体),Physics Collider(烘焙带有Collider的物体)。

    Nav Mesh ModifierVolume:

    在这里插入图片描述

    与NavMeshModifier的不同在于此脚本不再只作用于一个物体,而是一片区域。

    Nav Mesh Modifier:

    在这里插入图片描述

    属性:

    1. Ignore From Build:烘焙时无视此物体。
    2. Override Area:重写区域。如果勾选此选项,则在烘焙时Area层会采用下面的设置。
    3. Area Type:设置重写Area层。
    4. Affected Agents:适用的代理。

    Nav Mesh Link:

    用户不在需要自行添加起始点和终止点了。
    在这里插入图片描述

    属性:

    1. Agent Type:适用的Agent。
    2. Start Point:开始点坐标。
    3. End Point:终止点坐标。
    4. Swap:两极反转。
    5. Align Transform:Transform对齐,将该物体和startPoint,EndPoint对其在一条线上。
    6. Width:link宽度。
    7. Cost Modifier:修改花费值,负数代表使用Area默认的值。
    8. Auto Update Position:是否在开始游戏后动态更新位置。
    9. Bidirectional:是否双向。
    10. Area Type:Area类型。

    区域动态烘焙:

    Local Nav Mesh Builder:

    在这里插入图片描述

    属性:

    1. Tracked:区域要跟踪的Transform。
    2. Size:动态区域的大小。

    Nav Mesh Source Tag:

    在这里插入图片描述

    展开全文
  • 寻路算法简介

    2018-11-27 13:43:00
    寻路算法简介 对一个物体来说,移动很容易,而寻路很复杂。 为什么要寻找路径?考虑以下情况: 一个单位最初位于地图的底部,并希望到达顶部。 Movement - 它扫描的区域(肉色底)中没有任何阻挡...

    对一个物体来说,移动很容易,而寻路很复杂。

    为什么要寻找路径?考虑以下情况:

    一个单位最初位于地图的底部,并希望到达顶部。

    Movement - 它扫描的区域(肉色底)中没有任何阻挡表示该装置不应向上移动,因此它继续前进。在顶部附近,它会检测到障碍物并改变方向。然后它沿着(红色)路径绕过“U”形障碍物。

    Pathfinding - 另一个想法是,探路者扫描更大的区域(浅蓝底),发现较短的路径(蓝色),从而避免走进凹形障碍物。

     

    另外,您可以扩展移动算法以解决上面显示的陷阱问题。可以避免生成凹陷障碍物,也可以将它们的凸包标记为危险(只有在目的地位于内部时才进入):

     

    寻路的搜索器希望能够提前计划,而不是等到最后一刻发现障碍。

    我们需要在(Pathfinding)路径规划和(Movement)进行移动之间进行权衡。

    规划通常较慢,但能给出更好的路径;运动通常更快,但可能会卡住。

    如果游戏世界经常变化,那么提前规划就不那么有价值了。

    我建议同时使用:在拥有大型、移动缓慢的障碍物,以及起点到目标之间有很长的路径时用 Pathfinding;在局部区域、有快速变化和较短路径时用 Movement。

    算法

    新页面

    计科的教科书中,寻路算法,应用在图论中。

    图在数学意义上,是一组具有连接它们的边缘的顶点。

     

    平铺的游戏地图可以视为一张图。每个平铺块都是顶点,彼此相邻的图块之间有连接的边:

     

    现在,假设我们正在使用二维网格

    如果您之前没有使用图表,请参阅此入门手册。稍后,我将讨论如何从游戏世界中构建其他类型的图形

    来自AI或算法研究的大多数寻路算法,都是针对任意图形,而不是基于网格的游戏而设计的。

    我们想找到一些可以利用游戏地图性质的东西。

    我们认为有些事情是常识,但算法并不理解。我们对距离有所了解:一般来说,当两个东西相距较远时,假设没有虫洞,则需要更长时间才能从一个移动到另一个。我们对方向有所了解:如果您的目的地位于东方,那么走向东方的路径比走向西方更容易找到最佳路径。在网格上,我们知道关于对称性的东西:大多数时候,向北移动然后向东移动与向东移动然后向北移动相同。这些附加信息可以帮助我们更快地运行寻路算法。

    Dijkstra算法和最佳优先搜索

    Dijkstra 算法通过从对象的起点开始访问图中的顶点来工作。

    然后,它重复检查最近的尚未检查的顶点,将其顶点添加到要检查的顶点集

    从起点向外扩展,直到达到目标。

    Dijkstra 算法保证找到一条从起点到目标的最短路径,只要没有边缘具有负成本。(我写的是“一条最短路径”,因为通常存在多个等效短路径。)

    在下图中,粉红色方块是起点,蓝色方块是目标,蓝绿色区域显示Dijkstra算法扫描的区域。最轻的蓝绿色区域距离起点最远,因此形成了探索的“前沿”:

     

     

    贪心算法(Greedy Best-First-Search)以类似的方式工作,除了它有一些估计(称为启发式,任何顶点离目标有多远。它不是选择最接近起点的顶点,而是选择最接近目标的顶点)。

    贪心算法不保证找到最短的路径。

    然而,它比 Dijkstra算法运行得快得多,因为它用的启发式函数非常快速地引导它朝向目标。例如,如果目标位于起始位置的南侧,则贪心算法将倾向于关注向南的路径。

    在下图中,黄色表示具有高启发式值(达到目标的高成本)的节点,黑色表示具有低启发式值的节点(达到目标的低成本)。它表明,与Dijkstra的算法相比,贪心算法可以非常快速地找到路径:

    然而,这两个例子都说明了最简单的情况 - 当地图没有障碍物时,最短路径确实是一条直线。

    让我们考虑上一节中描述的凹陷障碍。Dijkstra的算法更加努力,但保证找到最短的路径:

    另一方面,贪心的Best-First-Search做的工作较少,但其路径显然不太好:

    麻烦的是贪婪的Best-First-Search是“贪心的”,试图朝着目标前进,即使它不是正确的道路。

    因为它只考虑到达目标的成本忽略了到目前为止的路径成本,所以即使它会继续前进,即便所使用的路径会变得非常长。

     

    将两者中最好的结合起来会不会很好?

    A *是在1968年开发的,用于结合启发式方法(如贪心算法)和其他更庄重些的方法(如Dijsktra算法)。

    这有点不寻常,因为启发式算法通常会为您提供一种解决问题的近似方法,而无法保证最优解。

    而 A* 建立在启发式的基础之上,虽然启发式本身并不能保证,但 A* 可以保证最短的路径。

     A* 算法

    我将专注于A* 算法。A* 是寻路寻找最受欢迎的选择,因为它非常灵活,可以在各种环境中使用。

    像 Dijkstra 算法一样,它可以用来找到最短的路径。像贪心算法一样,它可以使用启发式来指导自己。在简单的情况下,它与贪心算法一样快:

    在具有凹陷障碍物的示例中,A* 可以找到与Dijkstra算法找到的路径一样好的路径:

    它成功的秘诀在于它结合了Dijkstra算法使用的信息(支持接近起点的顶点)和贪心算法使用的信息(支持接近目标的顶点)。

    在谈论A *时使用的标准术语,g(n)表示从起点到任何顶点的路径的确切成本 nh(n)表示从顶点到目标的启发式估计成本 n

    在上图中,黄色点(h)表示远离目标的顶点,蓝绿色点(g)表示远离起点的顶点。

    A* 在从起点移动到目标时平衡两者。每次通过主循环,它检查 具有最低的顶点 f(n) = g(n) + h(n)

    本文的其余部分将探讨启发式设计,实现,地图表示以及与在游戏中使用寻路相关的各种其他主题。有些部分很充实,有些则相当不完整。

    posted on 2018-11-27 13:43 秋月疾风 阅读( ...) 评论( ...) 编辑 收藏

    转载于:https://www.cnblogs.com/xuuold/p/10023648.html

    展开全文
  • 导航网格简介 RecastNavigation: https://github.com/recastnavigation/recastnavigation 谷歌开源的一款非常强大的寻路系统,被广泛的应用于各大游戏引擎中 demo 中的素材是取自该系统 Babylo...
  • 调研了下,大概有两个插件可以用于Unity2D: 1.PolyNav - 2D Pathfinding 2.Navigation2D Pathfinding 当然,这些插件包括unity自带的Navmesh,还有那个著名的A start pathfind 插件,都是只用于客户端,不能...
  • C# 推箱子 自动寻路

    2013-12-16 09:54:34
    具有自动寻路功能的推箱子算法 使用A 寻路算法 效果并非最优 但是希望可以给大家一些启发 有问题或建议欢迎站内联系 或电邮chenc9410@gmail com 希望对大家学习人工智能或者C#有帮助 附:算法简介 忽略了...
  • 最近开始接触寻路算法,对此不太了解的话建议读者先看这篇文章 《如何快速找到最优路线?深入理解游戏中寻路算法》 。所有寻路算法都需要一种方法以数学的方式估算某个节点是否应该被选择。大多数游戏都会使用 启发...
  • 塔防游戏中寻路的实现

    千次阅读 2021-11-07 20:57:30
    寻路设计简介 多边形裁剪 - Vatti 多边形三角化 - 耳切法 三角化后的最短路径搜索 -Dijkstra 路径平滑 - 漏斗法 源码:GitHub - Dead-Rabbit/MineNavMesh: 个人关于 寻路 的学习 前情提要 游戏的塔防需要...
  • 还生成导航多边形数据 为何不直接利用obj中的三角形数据,原因可能如下: 1 obj中的三角形数据可能细节更多,而导航寻路可以适当简化多边形细节,提高效率 2 寻路有对象宽度限制,体素化利于处理 3 obj中没有包含layer...
  • 深入理解游戏中寻路算法(转)

    万次阅读 2019-03-23 11:51:41
    这种看似寻常的寻路在程序实现起来就需要一定的寻路算法来解决,如何在最短时间内找到一条路径最短的路线,这是寻路算法首先要考虑的问题。 在这篇文章中我们会循序渐进来讲解寻路算法是如何演进的,你会看到一种...
  • 1.DEMO简介 本DEMO使用Three.js作为主要开发工具,开发过程主要分为两个部分: 首先是使用Three.js实现A*寻路算法,效果图如下: 具体功能: 1.自动生成地图 2.根据选定开始及结束位置计算路线(涉及构造器,...
  • 寻路系统是游戏常用功能 (魔兽争霸,王者荣耀,MMO等项目) 也是游戏开发者的必备技能 这期我们花5分钟掌握LAYA如何使用寻路系统 寻路算法使用了pathfinding.js github 地址:...
  • JPS寻路算法优化思路

    2021-09-12 01:21:52
    寻路算法成为瓶颈的时候,可以看看JPS算法是怎么解决寻路过程中的性能问题的
  • 寻路网格Nav Mesh的生成原理

    千次阅读 2019-09-19 16:11:10
    文章目录1 简介 这篇文章将会翻译一篇来自布莱金理工学院的论文Towards Real-Time NavMesh Generation Using GPU Accelerated Scene Voxelization的前一小部分。传统的NavMesh生成是在CPU上做的体素化,这篇文章主要...
  • Unity SWS自动寻路插件

    2021-05-27 14:49:57
    简介 Simple Waypoint System(SWS)是基于Dotween的一款路径动画插件,,SWS在Dotween的基础上实现了可编辑路径,并且支持自动检测2D和3D模式 使用 导入插件后,选择Window->Simple Waypoint System->...
  • 基于WebGL/Threejs AI寻路

    千次阅读 2019-06-17 15:05:21
    Threejs 寻路算法,可以帮助AI在你的场景世界里导航。它使用A*和漏斗算法来计算导航网格上的路径。 简介 传统上,游戏和3D应用程序使用路标来帮助它们的人工智能代理导航。这是不好的,有很多问题,但通常比导航...
  • 文章目录一、本篇目的二、开发环境三、简介四、程序结构五、寻路库的使用1、库添加到引用2、例子13、例子24、例子3六、使用`Excel`画地形图 一、本篇目的 学习了A*寻路基础之后,发现源码下载不了了,自己实现一下,...
  • 一、A*算法的一个应用实例:迷宫寻路【下面是A*算法的一个应用实例:迷宫寻路。在日趋流行的3D游戏中,如何使非玩家控制角色准确实现自动寻路功能成为3D 开发技术中一大研究热点。其中A*算法得到大量运用。A*算法与...
  • 关于A*寻路算法的代码在网上有很多,但用DELPHI的比较...A*寻路算法简介 A*与最好优先算法的原理类似,只是最好优先算法在路经上给出了节点的代价,而A*算法需要F(NODE) = G(NODE)+H(NODE)的估价函数来估计当前点的代价
  • 流场简介流场,一般为网格图,网格中的每一个节点包含一个向量,该向量是物体在该位置时期望的速度。流场寻路利用流场的速度信息指导大量物体同时进行寻路。换句话说,如何生成可以寻路的流场,才是问题的关键。这里...
  • Unity寻路

    2019-04-26 17:40:07
    现在的游戏玩家很多都需要一键寻路功能,主要是游戏地图越来越大,让玩家自己找路的话会耽误非常多的时间,带来不好的体验。 因此,只要场景不是非常简单,一般都会给玩家做一个...NavMesh简介 https://www.paws...
  • 在线学习 和 离线学习三、迷宫寻路问题简介四、强化学习求解思路五、java代码1.辅助类-Instance2.主类-Application3.运行结果展示 前言 相信大多数小伙伴应该和我一样,之前在学习强化学习的时候,一直用的是Python...
  • 算法简介 A*简单高效,可用于许多寻路算法中。 在这里我们共实现Node类,PriorityQueue类,NodeManager类和AStar类。 在Node类中,我们管理每个地图块的信息,包括是否为障碍、估值等。 PriorityQueue类用于储存处理...
  • AStar-寻路原理

    千次阅读 2020-01-09 14:27:27
    由于一次面试被问起AStar算法原理,我当场面红耳赤,不知怎么开口,这个耳熟能详的寻路算法,我对它的原理却浑然不知,一直都有听大家说到这个算法,也有调用过相关接口,然自己却那么陌生,真想一头钻到地底。...
  • 完整的Unity开发人员-第9节-Zombie Runner ...僵尸赛跑者简介 创建令人惊叹的3D地形。 内置字符控制器。 AI导航和寻路。 VR兼容的HUD界面。 物品领取。 第9节游戏设计文件 关于本文件... 游戏的简要说明。 可以随
  • Q-learning解决悬崖寻路问题一级目录二级目录三级目录 一级目录 二级目录 三级目录
  • 利用易语言大漠写游戏辅助,我们经常在NPC对话,切换城市,执行任务,之间离不开跑路寻路,但每个程序之间的衔接主要看是否到达目的地,也就是判断跑路是否停止,这样任务之间的衔接才能自然,通过大漠的命令...
  • Unity -- 导航寻路系统

    千次阅读 2017-07-31 18:05:23
    首先将Navigation面板找出来,步骤如下图 然后选择所有地方与障碍物,然后到Navigation面板的...上图中参数的简介 1. Agent Radius:代理半径,也可以说是代理的宽度 2. Agent Height:代理的高度 3. Max Slope:

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 975
精华内容 390
关键字:

寻路简介