[ Intergalactic_Planetary Editor]

procedural

(BluePrintRandom) #21

property mode is almost finished :smiley:


(BluePrintRandom) #22

pathfinding is done :smiley:

when you feature creep around whole planets, it’s important to use A* to get back.


(BluePrintRandom) #23

ok pathfinding had to be applied to arbitrary groups of points instead of tile KX_GameObject() so I had to replace object.getDistanceTo() and clean up a few things ( not itterate over a v_index, instead use a premade list)

:slight_smile: pathfinding working on a whole planet with quite a few nodes
about 1.2 ms to path the whole grid,

we will see if I can pop this into a coroutine and get this done over X frames so multiple agents can be pathfinding in 1 frame with no lag.


(CYNIC78) #24

Amazing stuff! You are BGE-wizard! :slight_smile:


(BluePrintRandom) #25

thanks! it turned out to be a bit worse performance than I could tolorate so I broke the nodes into 6 leaves with 98,000 ? nodes) /6
think sides of a cube

I next am splittin gthe 6 groups into 9 equal sized groups
(think subdividing a cubes faces)

this will make it 54 nodes instead of 6 for the ‘macropath’ and many less nodes traversed extra in the end


(BluePrintRandom) #26

ok good news bad news -

good news is, that it is indeed much much faster

bad news = it takes a long time to crunch the grid before the game starts

counter good news = we can save the graph to disk

counter bad news = if we edit the world we have to edit all graphs using that node in place

more good news - I can make this even faster by installing a co-routine

pathfinder[‘Que’]

agent registers self as pathfinding on que

que assigns coroutine -> when it finishes it pops the path in the agent and changes state to received path.

pathfinding agents may register for a new path while walking the old, allowing for seamless updates to path …

Soon we will be onto making a actual game again instead of a framework!!


(BluePrintRandom) #27

ok I found a nice plan C here

normal A*
I tried pathing all the nodes -
40 ms to path half way around the planet

I tried pathing major leafs of nodes, and then using that to call a graph that was just the needed nodes (cull nodes)

this was very fast at runtime but took up a lot of space and took a long time to pre-compute
4 minutes to store graphs - .5ms to path planet

hybrid approach = if you don’t have premade graph, create it and use it -> +1.5ms the first time it’s called -> .5 the next.

so it’s reasonably fast and it just gets faster the longer they play.


(BluePrintRandom) #28

added a que -


now
if graphKey in saveGraphs:
     pathfind
else:
     make graph
     pathfindnextframe()

(BluePrintRandom) #29

:maniacal laughter:

pathfinding course grain is working!

next is to write a tool to edit the nodes (major) and later we will path find vertex, so they will also need a blocked/ not blocked attribute.


(BluePrintRandom) #30

fine grain path finding working using 1 kdtree each pathfind it creates and uses 1 time to get the start / end nodes. (the end node is a target of the course grain path / macropath )

next up is instead forming a small kdtree per tile when needed, so it can be used over and over
(pathing a node the first time will be more expensive)

(so it should actually be much faster / smoother than this)