Navmesh / Pathfinding WIP

[Lapis the Floran]

Just quarter handicapped

Radical.  cant wait for the time when bot events get shoved into this so i can have a bunch of bots in different locations suppress fire on a window or follow and defend another bot.

[Ad Bot]

[cHeEsEpIzZa2]

definitely gonna make a stealth heist game once this is out

[Gytyyhgfffff]

Got storing nodes in C#, sending nodes to Blockland from C#, and collapsing nodes in C# figured out today.

Tomorrow I want to tackle sending brick bounding information over to C#, so I can do all the node calculations there. To replicate containerBoxEmpty I guess I'm just going to store all the bricks in memory by their bounding box and check to make sure none of them intersect with the container box.

This will end up as a nested loop though when generating nodes for every brick though, how could this be improved?

i'm not too exactly sure what loop structure you're thinking of but you could certainly improve a containerBoxEmpty search by implementing a chunking system. essentially, imagine cubes of one size being tessellated infinitely. each brick that you add can be assigned to one of those cubes. how we're able to do this is through some mathematics. you have a map of vector3 -> cube and determine which cube a brick goes in by floor(brick.position / cubeSize). when you create cubes on the fly, you're able to assign bricks to these cubes and from there you can implement an efficient containerBoxEmpty search. this works because containerBoxEmpty, instead of looking through every single brick, would only look in the cubes whose bounds intersect with it. so instead of checking every single brick, you might only have to check say 4 cubes which will have way less bricks than the entire map contained within them. under the hood, that's how TS does these calculations itself more or less. they probably use octrees, which are just basically more advanced cubes. the thing about brick density in a build is its obviously not constant. you will have some areas which are sparsely populated and some areas that are densely populated. what an octree does is dynamically scale its cubes based on density of the bricks, which squeezes some additional performance out of the original chunking algorithm. iirc, it tries to keep a somewhat constant density in its cubes. so cubes will be scaled down if there's higher density in an area, resulting in more cubes but each cube will have a relatively constant number of bricks within it. for sparse areas, the cubes will be way larger in order to maintain the constant density. they behave in the exact same way the quad-tree nodes you implemented behave, except octrees are in 3d instead of 2d

all that being said you will not have to program any of this yourself. there are for sure c# libraries out there that you can exploit that will do all of this and more. to get you started on your search, you might want to look for collision checking libraries or something along those lines. octrees are basically necessary for collision engines because of the aforementioned density problems and you'll probably have a lot of luck starting your search there

[PhantOS]

can you add bsmod executions to blockland

when will blockland support mc data packs

[jackrobbman]

*Eating bowl of cereal, wishing bots weren't so stupid*

*Sees thread*

*Thread is still getting replies*

*Drops spoon in bowl, mouth agape*

*Sobs in relief*

The...the chosen ones....they're doing it!

[Crook]

Still working on this btw but progress is pretty boring/slow - currently refactoring everything so nodes are stored via global vars instead of scriptobjects which is significantly faster, but a bit more difficult to manage.

Also wrote a nodemap generator for the C# server, so nodes can be created outside of Blockland. Even in it's currently very inefficient state, it's much faster than Torque.

[Crook]

currently refactoring everything so nodes are stored via global vars instead of scriptobjects which is significantly faster, but a bit more difficult to manage.

(Mostly) finished doing this. New nodes are global vars referenced in double linked list instead of scriptobjects. New benchmarks
ATC Fort: 1070ms
Afghan DM: 70 seconds

Should be really fast and easy to transfer from the C# server if I bother writing out a better container search

[Kyuande]

Got storing nodes in C#, sending nodes to Blockland from C#, and collapsing nodes in C# figured out today.

Tomorrow I want to tackle sending brick bounding information over to C#, so I can do all the node calculations there. To replicate containerBoxEmpty I guess I'm just going to store all the bricks in memory by their bounding box and check to make sure none of them intersect with the container box.

This will end up as a nested loop though when generating nodes for every brick though, how could this be improved?

Unfortunately if I remember (correct if I'm wrong) the engine for general container box searching likes to scan every object in the game and see if it's even in the zone (which is why your server lags after a certain amount of bricks per scan)

You can implement your information to C# scope once a brick plants; when the brick is deleted the information is also sent into the C# scope.
Your C# scope will of course do a lot of this processing work since now you have more information what you stored per brick.
The downside here though is when you're creating a lot of bricks at once, this may reduce performance.

[Conan]

live blockland almost certainly doesn’t do the scan all for searches - if badspot got kompressor to write an oct tree id doubt hed neglect to use it for searching. its clear theres an oct tree running for bricks anyways given that some of the visual debug stuff is still there and you can turn it on and watch the octree grow when you place down bricks.

you’re likely thinking of the version of tge that blockland started development off of - that definitely had that sort of search “algorithm” except it was a tad bit smarter using a set number of bins. however that also meant it assumed the world would only be so large/have so many objects considering the bin count was like 256 or something

[Crook]

Saw someone working on navmesh stuff earlier today so I figured I would release this in case people want to look at it
Haven't finished moving save and pathfinding features over to the new globalvar system so theyre not working right now

https://leopard.hosting.pecon.us/dl/xvwus/System_Wrathfinder.zip

General usage:
wrath_generateNavmesh(); - builds nodemap and links
wrath_showNodeShapes(); - shows nodes as yellow or blue (crouch) rectangles
wrath_showNodeLinks(); - shows node links as green lines

Contains the old version of shapelines - not sure if that will cause conflicts

[Crook]

Quick reference on nodes and how to access them
Nodes are a series of global variables and have an associated index. The amount of nodes present is stored in $nodes. Node IDs are stored in a double linked list

$nodePosition[ %node ] - Position of node in the world
$nodeX[ %node ] - Size of node on X axis
$nodeY[ %node ] - Size of node on Y axis
$nodeCrouch[ %node ] - Whether or not you have to be crouching to occupy this node's space
$nodeHeight[ %node ] - Z position of node
$nodeNeighbors[ %node ] - Amount of links this node has

$nodeNeighbor[ %node SPC %i ] - Linked node %i
$nodeNeighborEdge[ %node SPC %neighbor ] - The edge this node shares with %neighbor
$nodeNeighborAxis[ %node SPC %neighbor ] - Two booleans specifying which cardinal direction neighbor %neighbor is in relation to %node

$nodeYMax[ %node ] - The y element of the northern edge
$nodeYMin[ %node ] - The y element of the southern edge
$nodeXMax[ %node ] - The x element of the eastern edge
$nodeXMin[ %node ] - The x element of the western edge

(edges are represented x1 y1 z1 x2 y2 z2)
$nodeEdgeN[ %node ]  - The north edge
$nodeEdgeE[ %node ] - The east edge
$nodeEdgeS[ %node ] - The south edge
$nodeEdgeW[ %node ] - The west edge

Some misc crap
$nodeShape[ %node ] - The static shape for each node when debug shapes are drawn
$nodeAtPosition[ %position ] - The node found at %position

For the linked list:
$nodeLLStart - The start node in the LL
$nodeLLNext[ %node ] - The next node after %node in the LL
$nodeLLPrevious[ %node ] - The previous node before %node in the LL
wrath_printLL(); - Prints the linked list

How I iterate through the LL. Checking the position for null might be unnecessary

Code: [Select]

for(%i = $nodeLLStart; $nodePosition[ %i ] !$= ""; %i = $nodeLLNext[ %i ])

Creating/deleting nodes:
wrath_createNode(%position, %x, %y, %crouch)
wrath_deleteNode(%node)

Code is a little messy, sorry

[Night_Hawk]

Interesting concept! What could this be used for? Improvement to Slayer Team Bot AI I.E.?

[Crook]

Yeah, the idea would be to implement a path-finding algorithm on-top of the mesh and pass off paths to bots so they can from point A to B avoiding obstacles

Ports A* can pathfind through the mesh and return a list of nodes the bot must visit to reach the goal. Then, to get from one node in the path to the next, you'd find the shared edge between the nodes and direct the bot there.

[Badspot]

Bump

[TlTO]

Rallypack endorsed by Badspot? This changes everything.