Multi object pathfinder with ability to zip many small graphs into bigger graphs on the fly

Pahting_object_quads_with_zip_tested.blend (595.0 KB)

still a wip but it’s just about something special.

1 Like

Pahting_object_quads_with_zip_tested_upbge.blend (608.7 KB)

this pathfinder supports quads.

1 Like

A_Star_pathfind_object_quad.blend (604.9 KB)

ok this has the optimizations :smiley:

if start and goal on same object - pathfind just object

if start obejct and neighbor object are connected - pathfind object 1 + object 2’s nodes

if start and end are not connected, path find objects, use object path to assemble graph of path objects
(IE [Tile_1, Tile_2, Tile_3 ])

ok so now I am doing the following.

if the player is closer than a set distance -> pathfind world tiles by zipping them together
and check the obstacles table (obstacles not yet in table but will be stored as )

obstacles = [ (Tile#, Face#) ]

this is then discarded during graph forming

(this is why the smallest level pathfinding grids are not re-used)

graphs are gathered and cached for macro pathinding, and KDTree and edges are saved per tile to zip together the graph as well as to quickly get the location of a actor to mark as obstucted.

worldKD.find(actor.worldPosition) - yeilds tile
tileKDTree -> yields face to mark as obstructed.
some balancing is in order as well as potentially saving KDTree and graph objects to disk some how
so they never need to be calculated by the end user.

Macro [objects]-
Micro[object faces] -
Nano [subdivided patch ‘skinning’ a microface with 64 quads.]

if a player is far away - and not on the next object over - path all objects
create graph that is just returned path objects pathfind this for macropath

all the heavy stuff is in a coroutine.


this should set you up nicely

the nodes don’t have to be a grid, just quads so ‘roads / paths’ should work fine.
I use straight line distance in my cost function intially and then the true cost is gathered first time you path

1 Like

Wow thanks, that’s some pretty nice setup. This is great for roads indeed.

1 Like

Bump - this is actually really really efficent,
(you can traverse a single graph if the object is on the same pathing graph as the original,
if they are on a adjacent graph, it paths only the 2 graphs, and beyond that it uses A* to path the graphs themselves, to get what graphs to use to build a composite graph if it’s not already generated)

one corner case I need to plan for, is if both objects are on 1 graph, yet the path must traverse another adjacent graph and come back.