forum.boolean.name
Страница 1 из 3 1 23 >
Показывать 64 сообщений этой темы на одной странице

forum.boolean.name (http://forum.boolean.name/index.php)
-   3D-программирование (http://forum.boolean.name/forumdisplay.php?f=12)
-   -   Искуственный интеллект (http://forum.boolean.name/showthread.php?t=17810)

burovalex 29.01.2013 08:55
Искуственный интеллект
 
Вложений: 1
Доброго времени уважаемые буленчане!

Хочу реализовать ИИ на движке Блитц3Д+Ксорс+Физикс.
Помогите обойти грабли, на которые вы сами наступали при такой реализации.

Хотелось бы реализовать как на рисунке справа.
Сложно ли это будет сделать?
Стоит ли маршрут просчитывать динамически в реалтайме, либо строить вейпоинты?
Если вейпоинты, то где их удобнее хранить, в самом типе ИИ либо в отдельном массиве?
Для прогнозирования встречи с препятствием что лучше использовать, Pick,Collided(Xors'a), RayCast(PhysX'a)?

DarkInside 29.01.2013 11:49
Ответ: Искуственный интеллект
 
Кури A* - самое простое для новичка
http://ru.wikipedia.org/wiki/%D0%90%...D0%BA%D0%B0_A*

Или если хочешь повозиться с матрицами, то волновой аглогитм
http://ru.wikipedia.org/wiki/%D0%92%...B8%D1%82%D0%BC

burovalex 29.01.2013 12:09
Ответ: Искуственный интеллект
 
Ребят, можно без всякого научного бреда?
Может в математике это эффективно, но если ты начнешь проверять как в вики каждую точку на пересечение с объектом в 3д мире - комп загнётся от таких А-звезд и волновых эффектов.

А вообще такие методы у меня изображены на левом рисунке.
По сути я могу спокойно двигать ncp пока он не упрётся в стену -> если упёрся повернуть в сторону -> пройти прямо -> поворачиваться к цели -> упёрся -> ....
Работать будет Намного быстрее

Raion 29.01.2013 12:23
Ответ: Искуственный интеллект
 
Ну тогда используй точки перемещения. Самый простой и быстрый вариант.Только персонажи будут бегать по одной линии следования. Или тебе нужна готовая библиотека поиска пути.

burovalex 29.01.2013 12:28
Ответ: Искуственный интеллект
 
Да хоть что-нибудь чтоб оттолкнуться..

Как понимать Точки перемещения??

Gector 29.01.2013 12:44
Ответ: Искуственный интеллект
 
Цитата:
Сообщение от burovalex (Сообщение 251036)
Работать будет Намного быстрее
Не будет. Пик будет жрать не так уж и мало ресурсов.
Кстати можно было и поискать по форуму. Астар на блице.

burovalex 29.01.2013 13:01
Ответ: Искуственный интеллект
 
Ну и что, астар.. Ты понимаешь какой в методе принцип складывается. Что для блитца на такой метод надо кучу ентити создать и проверять между ними расстояние, а теперь добавь туда еще и препятствия и получится попа!

H@NON 29.01.2013 13:09
Ответ: Искуственный интеллект
 
тебе для вейпоинта(точки перемещения) нужны лишь координаты, никакие ентити тут не нужны

burovalex 29.01.2013 13:21
Ответ: Искуственный интеллект
 
Вложений: 1
Давайте я попробую пример сделать, на основе (если помните по информатике проходили) типа метод пузырька или чтото вроде того
Хочу попробывать так, как на рисунке в аттаче

Но для этого надо будет добавлять чтото типа графов

Подскажите только плиз как в тип добавлять подтипы?
Т.е. маленький пример, я пойму, просто не хочется гуглить с моим мертвым интернетом..

jimon 29.01.2013 13:29
Ответ: Искуственный интеллект
 
burovalex
в кваке третей поиск пути был через пространственных граф параллелепипедов которые задавали объемы в которых мог свободно гулять персонаж, а связи между объемами - это как персонаж должен перейти (например прыжок или присесть)

отсюда боты из третей кваки работали на любой карте, и это не тормозило в 1999, почему более простой алгоритм (Astar) будет тормозить у тебя в 2013 ?
а то что ты показал в первом посте на левой и правой карте это всего лишь как персонаж идет по найденому пути, достаточно идти по квадратному пути с простой кубической интерполяцией и получишь то что на правой части картинки

ps. алгоритмы поиска пути всегда работают на графах, в том числе и Astar, то что он в статьях для блица ищет по 2д массиву - просто абстракция чтобы упростить понимание

burovalex 29.01.2013 14:25
Ответ: Искуственный интеллект
 
Наверное надо было уточнить, что мой мир динамичный - с растущими деревьями, и меняющимися препядствиями. Вот теперь представь выросший небольшой лесок, надо обойти деревья. Как в кваке со статичной картой такое не проканает, ну точнее надо будет постоянно обновлятьих, да и придется всё таки создавать ентити кучу.
А мне то надо сделать так, чтобы встретил зверушку, она шугнулась, и начала строить себе маршрут отступления.

burovalex 29.01.2013 14:43
Ответ: Искуственный интеллект
 
Вот у меня сейчас терраин 64х64 и это так - средненький островок.
Использую я конечно 30-40% суши, НО я сейчас тестил этот пример Астар
и он выдал время обработки 4 мс - вот теперь прикинь что будет допустим 5 шуганутых зверюшек - и комп повесится

вот исходник со встроенным Астаром

Код:
Graphics3D 1024, 768, 32, 2
SetBuffer BackBuffer()


;        Create navigation grid
Local rows=64
Local cols=64
       
Dim Graph.NAV_Node(rows, cols)

For col=0 To cols-1
        For row=0 To rows-1
                Graph(col, row)=NAV_CreateNode(col*10, 0, row*10)
               
                ;Swap pivot with cube to make node visible
                FreeEntity Graph(col, row)\Pivot
                Graph(col, row)\Pivot=CreateCube()
                PositionEntity Graph(col, row)\Pivot, col*10+Rnd(-2, 2), 0, row*10+Rnd(-2, 2)
        Next
Next

;        Connect nodes
For col=0 To cols-1
        For row=0 To rows-2
                NAV_Connect(Graph(col, row), Graph(col, row+1))
        Next
Next
       
For row=0 To rows-1
        For col=0 To cols-2
                NAV_Connect(Graph(col, row), Graph(col+1, row))
        Next
Next

;        Set camera
Camera=CreateCamera()
PositionEntity Camera, rows*10/2, rows*10, cols*10/2
TurnEntity Camera, 90, 0, 0

;        Pick source and destination nodes

Src.NAV_Node=Graph(0, 0)
Dst.NAV_Node=Graph(rows-1, cols-1)

EntityColor Src\Pivot, 0, 0, 255
EntityColor Dst\Pivot, 255, 0, 0

;        Get search time

time1=MilliSecs()
NAV_FindPath(Src, Dst)
time2=MilliSecs()

P.NAV_Node=Dst\Parent

While P<>Null
        EntityColor P\Pivot, 255, 0, 0
        P=P\Parent
Wend

While Not KeyHit(1)
        UpdateWorld
        RenderWorld
        Text 20, 20, "time: "+(time2-time1)
        Flip
Wend
End

;        NAVIGATION

Type NAV_Node
        Field Pivot
        Field Disabled
        Field Parent.NAV_Node                        ; for path building
        Field F#, G#, H#
       
        Field FirstLink.NAV_Link
        Field LastLink.NAV_Link
End Type

Type NAV_Link
        Field Node.NAV_Node
        Field Distance#
       
        Field PrevLink.NAV_Link
        Field NextLink.NAV_Link
End Type

Type NAV_OpenedNode
        Field Node.NAV_Node
End Type

Type NAV_ClosedNode
        Field Node.NAV_Node
End Type

Type NAV_Path
        Field StartNode.NAV_PathNode
End Type

Type NAV_PathNode
        Field Node.NAV_Node
       
        Field NextNode.NAV_PathNode
End Type

Function NAV_CreateNode.NAV_Node(X#, Y#, Z#)
        Local Node.NAV_Node=New NAV_Node
        Node\Pivot=CreatePivot()
        PositionEntity Node\Pivot, X, Y, Z
        Return Node
End Function

Function NAV_AddLink(NodeA.NAV_Node, NodeB.NAV_Node)
        Local Link.NAV_Link=New NAV_Link
        Link\Distance=EntityDistance(NodeA\Pivot, NodeB\Pivot)
        Link\Node=NodeB
       
        If NodeA\LastLink<>Null
                Link\PrevLink=NodeA\LastLink
                NodeA\LastLink\NextLink=Link
                NodeA\LastLink=Link
        Else
                NodeA\FirstLink=Link
                NodeA\LastLink=Link
        EndIf
End Function

Function NAV_Connect(NodeA.NAV_Node, NodeB.NAV_Node)
        NAV_AddLink(NodeA, NodeB)
        NAV_AddLink(NodeB, NodeA)
End Function

Function NAV_Heuristic#(Node.NAV_Node, DstNode.NAV_Node)
        Local X#=Abs(EntityX(DstNode\Pivot, True)-EntityX(Node\Pivot, True))
        Local Y#=Abs(EntityY(DstNode\Pivot, True)-EntityY(Node\Pivot, True))
        Local Z#=Abs(EntityZ(DstNode\Pivot, True)-EntityZ(Node\Pivot, True))
       
        Return (X+Y+Z)
End Function

Function NAV_AddToOpened(Node.NAV_Node)
        Local Opened.NAV_OpenedNode
        Local L.NAV_OpenedNode
        Local R.NAV_OpenedNode
       
        L=First NAV_OpenedNode
       
        If L<>Null
                If Node\F<=L\Node\F
                        Opened=New NAV_OpenedNode
                        Opened\Node=Node
                        Insert Opened Before L
                        Return
                EndIf
        Else
                Opened=New NAV_OpenedNode
                Opened\Node=Node
                Return
        EndIf
       
        Repeat
                R=After L
                If R=Null Then Exit
               
                If Node\F>=L\Node\F And Node\F<=R\Node\F
                        Opened=New NAV_OpenedNode
                        Opened\Node=Node
                        Insert Opened Before R
                        Return
                EndIf
                L=R
        Forever
       
        Opened=New NAV_OpenedNode
        Opened\Node=Node
       
End Function

Function NAV_AddToClosed(Node.NAV_Node)
        Local Closed.NAV_ClosedNode
        Local L.NAV_ClosedNode
        Local R.NAV_ClosedNode
       
        L=First NAV_ClosedNode
       
        If L<>Null
                If Node\F<=L\Node\F
                        Closed=New NAV_ClosedNode
                        Closed\Node=Node
                        Insert Closed Before L
                        Return
                EndIf
        Else
                Closed=New NAV_ClosedNode
                Closed\Node=Node
                Return
        EndIf
       
        Repeat
                R=After L
                If R=Null Then Exit
               
                If Node\F>=L\Node\F And Node\F<=R\Node\F
                        Closed=New NAV_ClosedNode
                        Closed\Node=Node
                        Insert Closed Before R
                        Return
                EndIf
                L=R
        Forever
       
        Closed=New NAV_ClosedNode
        Closed\Node=Node
End Function

Function NAV_SortNode(Opened.NAV_OpenedNode)

        Local Node.NAV_Node=Opened\Node
        Delete Opened
       
        Local L.NAV_OpenedNode
        Local R.NAV_OpenedNode
       
        L=First NAV_OpenedNode
       
        If L<>Null
                If Node\F<=L\Node\F
                        Opened=New NAV_OpenedNode
                        Opened\Node=Node
                        Insert Opened Before L
                        Return
                EndIf
        Else
                Opened=New NAV_OpenedNode
                Opened\Node=Node
                Return
        EndIf
               
        Repeat
                R=After L
                If R=Null Then Exit
                       
                If Node\F>=L\Node\F And Node\F<=R\Node\F
                        Opened=New NAV_OpenedNode
                        Opened\Node=Node
                        Insert Opened Before R
                        Return
                EndIf
                L=R
        Forever
       
        Opened=New NAV_OpenedNode
        Opened\Node=Node
       
End Function

Function NAV_IsOpened.NAV_OpenedNode(Node.NAV_Node)
        For Opened.NAV_OpenedNode=Each NAV_OpenedNode
                If Opened\Node=Node Then Return Opened
                If Opened\Node\F>Node\F Then Return Null
        Next
End Function

Function NAV_IsClosed(Node.NAV_Node)
        For Closed.NAV_ClosedNode=Each NAV_ClosedNode
                If Closed\Node=Node Then Return True
                If Closed\Node\F>Node\F Then Return
        Next
End Function

Function NAV_FindPath.NAV_Path(SrcNode.NAV_Node, DstNode.NAV_Node)
        Local Node.NAV_Node
        Local Link.NAV_Link
        Local LinkNode.NAV_Node
        Local Opened.NAV_OpenedNode
        Local Closed.NAV_ClosedNode
       
        NAV_AddToOpened(SrcNode)
       
        Local Fail
       
        Repeat
                Opened=First NAV_OpenedNode
               
                If Opened=Null
                        Fail=True
                        Exit
                EndIf
               
                Node=Opened\Node
                Link=Node\FirstLink
               
                Delete Opened
                NAV_AddToClosed(Node)
               
                While Link<>Null
                       
                        LinkNode=Link\Node
                        If LinkNode\Disabled=False
                                If NAV_IsClosed(LinkNode)=False
                                        Local G=Node\G+Link\Distance
                                       
                                        If LinkNode=DstNode
                                                LinkNode\Parent=Node
                                                Exit
                                        EndIf
                                       
                                        Local OpenedLinkNode.NAV_OpenedNode=NAV_IsOpened(LinkNode)
                                       
                                        If OpenedLinkNode=Null
                                                LinkNode\Parent=Node
                                                LinkNode\G=G
                                                LinkNode\H=NAV_Heuristic(LinkNode, DstNode)
                                                LinkNode\F=LinkNode\G+LinkNode\H
                                                NAV_AddToOpened(LinkNode)
                                        Else
                                                If G<LinkNode\G
                                                        LinkNode\Parent=Node
                                                        LinkNode\G=G
                                                        LinkNode\F=LinkNode\G+LinkNode\H
                                                        NAV_SortNode(OpenedLinkNode)
                                                EndIf
                                        EndIf
                                EndIf
                        EndIf
                       
                        Link=Link\NextLink
                Wend
               
                If LinkNode=DstNode Then Exit
        Forever
       
        If Fail=False
                Local Parent.NAV_Node=DstNode
               
                If Parent=Null Then RuntimeError ""
               
                Local PathNode.NAV_PathNode=New NAV_PathNode
                PathNode\Node=Parent
               
                Local NextNode.NAV_PathNode=PathNode
               
                Repeat
                        Parent=Parent\Parent
                        PathNode=New NAV_PathNode
                        PathNode\Node=Parent
                        PathNode\NextNode=NextNode
                        NextNode=PathNode
                Until Parent=SrcNode
               
                Local Path.NAV_Path=New NAV_Path
                Path\StartNode=PathNode
               
                Delete Each NAV_OpenedNode
                Delete Each NAV_ClosedNode
               
                Return Path                                                                ; Finally return path
        Else
                Delete Each NAV_OpenedNode                                ; ...Or null
                Delete Each NAV_ClosedNode
        EndIf
End Function

Function NAV_NearestNode.NAV_Node(Entity)
        Local MinDistance#=10^38
        Local NearestNode.NAV_Node
       
        For Node.NAV_Node=Each NAV_Node
                If Node\Disabled
                        Local Distance#=EntityDistance(Entity, Node\Pivot)
                        If Distance<MinDistance
                                MinDistance=Distance
                                NearestNode=Node
                        EndIf
                EndIf
        Next
       
        Return NearestNode
End Function

Function NAV_DeletePath(Path.NAV_Path)
        Local PathNode.NAV_PathNode=Path\StartNode
        Local NextPathNode.NAV_PathNode
       
        While PathNode<>Null
                NextPathNode=PathNode\NextNode
                Delete PathNode
                PathNode=NextPathNode
        Wend
       
        Delete Path
End Function

Function NAV_Clear()
        For Node.NAV_Node=Each NAV_Node
                FreeEntity Node\Pivot
                Delete Node
        Next
       
        Delete Each NAV_Link
        Delete Each NAV_Path
        Delete Each NAV_PathNode
End Function

burovalex 29.01.2013 14:57
Ответ: Искуственный интеллект
 
Так на вопросы и не ответили

Цитата:
Если вейпоинты, то где их удобнее хранить, в самом типе ИИ либо в отдельном массиве?
Для прогнозирования встречи с препятствием что лучше использовать, Pick,Collided(Xors'a), RayCast(PhysX'a)?
Цитата:
Подскажите только плиз как в тип добавлять подтипы?
Т.е. маленький пример, я пойму, просто не хочется гуглить с моим мертвым интернетом..

DarkInside 29.01.2013 15:12
Ответ: Искуственный интеллект
 
Цитата:
Сообщение от burovalex (Сообщение 251036)
Ребят, можно без всякого научного бреда
Уважаемый, этот "научный бред" широко применяется на практике и неоднократно обсуждался на форуме

http://forum.boolean.name/showpost.p...50&postcount=2

Как уже сказали, если тебе нужно примитивное перемещение по вейпойнтам, тогда о каком "искусственном интеллекте" идет речь?

SBJoker 29.01.2013 15:40
Ответ: Искуственный интеллект
 
В играх типа Doom3 и прочих, нафигация монстров по коридорам и игре вобщем сделана вейпоинтами, с поиском пути по ним и прочее.
А микро-перемещения реализуются уже анализом положения преград по близости.
Подскочить к игроку например, или окружить его, поползать по стенам.


Часовой пояс GMT +4, время: 00:15.
Страница 1 из 3 1 23 >
Показывать 64 сообщений этой темы на одной странице

vBulletin® Version 3.6.5.
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Перевод: zCarot