search

MovingBlocks / Terasology

Terasology - open source voxel world
http://terasology.org
Apache License 2.0
3.68k stars 1.34k forks source link

AI - A*-based pathfinding algorithm #76

Closed Cervator closed 11 years ago

Cervator commented 12 years ago

First stab at actual AI. The A* algorithm (http://en.wikipedia.org/wiki/A*) seems like it might be usable in our 3D world of block coordinates if it is made to accept differing values depending on the terrain (sharp z-level changes or water would be undesirable states) and aim to arrive at Wayblocks from #75 (which would be a likely prerequisite)

Of course, I could be completely wrong and just remembering the term from going through https://www.ai-class.com so anybody feel free to research and post findings, ideas, and maybe even existing implementations / libraries we can use in the Dev Forum at http://board.movingblocks.net/viewforum.php?f=4

One question in particular is performance as the world is big, there will likely be many creatures, and they can't all re-calculate their pathfinding every other moment

t3hk0d3 commented 12 years ago

Perfomance issue is fixed quite simply: apply complex pathfinding alghoritm only on real need (like pathfinding to target).

Just walking around could be done using simpler alghoritms.

Cervator commented 12 years ago

Yeah, I figured we'd end up doing something like that. Any interest in helping out with more specific research or even implementation? :D

t3hk0d3 commented 12 years ago

@Cervator For sure :D When i'll got some additional spare time.

Cervator commented 12 years ago

Woot! Consider yourself on "the list" :D

t3hk0d3 commented 12 years ago

Just wanna say im already working on it.

Also related article http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php

Cervator commented 12 years ago

Great! I've tagged this issue with your name then :-)

Article looks very relevant to our mutual interests. Good stuff, and good luck! Ask away in the forum for more details / suggest approaches freely, etc :-)

t3hk0d3 commented 12 years ago

Also good article http://www.isprs.org/proceedings/xxxvii/congress/4_pdf/165.pdf

t3hk0d3 commented 12 years ago

Intermediate result. Still having some issues (perfomance is poop atm)

http://dl.dropbox.com/u/19947101/pathfinding.png

shrooms are blocks which processed during pathfinding

Cervator commented 12 years ago

Relates to commit: https://github.com/t3hk0d3/Terasology/commit/6892cd37aef9034c8d84df2f7a3317650cf75520

Cervator commented 11 years ago

In the long time since this was made we've had working pathfinding by @overdhose in miniions and now a whole pathfinding module by @synopia - closing as complete :-)