[ Intergalactic_Planetary Editor]

Game Engine Works in Progress and Game Demos
21

property mode is almost finished :smiley:

22

pathfinding is done :smiley:

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

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.

24

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

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

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!!

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.

28

added a que -


now 
if graphKey in saveGraphs:
     pathfind
else:
     make graph
     pathfindnextframe()
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.

1 Like
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)

2 Likes