Извините, ничего не найдено.

burovalex · 29.01.2013, 08:55

Доброго времени уважаемые буленчане!

Хочу реализовать ИИ на движке Блитц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

Работать будет Намного быстрее

Не будет. Пик будет жрать не так уж и мало ресурсов.
Кстати можно было и поискать по форуму. Астар на блице.

burovalex · 29.01.2013, 13:01

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

H@NON · 29.01.2013, 13:09

тебе для вейпоинта(точки перемещения) нужны лишь координаты, никакие ентити тут не нужны

burovalex · 29.01.2013, 13:21

Давайте я попробую пример сделать, на основе (если помните по информатике проходили) типа метод пузырька или чтото вроде того
Хочу попробывать так, как на рисунке в аттаче

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

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

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

Ребят, можно без всякого научного бреда

Уважаемый, этот "научный бред" широко применяется на практике и неоднократно обсуждался на форуме

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

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

SBJoker · 29.01.2013, 15:40

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