#Realtime Collision Detection inside a Pathfinding Grid

1 messages · Page 1 of 1 (latest)

winged geyser
#

Hey There,
Im making a 3D Pathfinding Grids System based on Unity Jobs and Burst , now the whole thing works very efficient and performant, now i want to implement a realtime collision detection system, which updates the grid based on the obstacles. I cant regenerate the whole grid because it would be not performant at all. Any ideas and Sources?

haughty zodiac
#

what are you storing in the grid that requires updating the entire grid when you add obstacles?

winged geyser
#

Its not nessesary needed to update the whole grid, and it will not work if i would do it that way. I currently have a NativeArrays which holds the Cells and i have another NativeArray which holds a unsafe list of neighbors per CellIndex, now i want to be able to just update the cells, which get covered by the obstacle, as im aiming for maximal performance, but im currently unable to find a good solution for it

haughty zodiac
#

I'm not sure I understand what you mean, but typically for these kinds of problems you would subdivide the data into blocks (i.e. octree-like structures); you then need to update the affected blocks and their neighbours but not the rest

#

do you mean you have a single native array with all the cells?

winged geyser
#

So you mean checking which "Cores" the obstacle overlaps and updates the Cells affected?

#

Yeah i currently have a Array for all Cells of the Grid, and another Array which stores the Neighbors of the CellIndex

haughty zodiac
#

okay, so one approach is to store your cells differently

I'll write a small overview of how this could work, but there are different and probably better approaches; I think this is intuitive and relatively simple to get into though.

  1. make it so you can index cells by world position if you havent already (e.g. (1.3, 2.5, -1.4) could become (1, 3, -2) for cells of size 1)
  • This makes it so you don't need to store neighbouring indices (since we can easily calculate them by adding/removing indices)
  1. subdivide the world into blocks of, say, 8x8x8 cells (this depends entirely on your use case); every block could store a flat array of cells; the blocks can also be stored in a flat array.
  • now neighbours are not that far away in memory
  • when updating the grid you only need to update one block, and perhaps one or more neighbouring blocks
#

Honestly I'm not sure I understood your problem well, I hope perhaps it helps ^^'

#

if you are looking for online resources, you could try looking for quadtree/octree in combination with A* or pathfinding

sacred eagle
#

crazy thought, but couldn't you save a world-space position of each cell, query the grid against the obstacle (so basically a proximity to any obstacles bound points) and have them marked obstructed?

#

and also what BuxXy said, dividing the entire grid to some smaller chunks so that only a part of it has to be queried etc.

Basically using some common approaches to have a much faster solution during run-time at a cost of pre-computing and saving some extra data about the grid

haughty zodiac
winged geyser
#

So basically i have a adjustable Grid with some parameters (length, height, widht, CellSize etc) and i got a static environment, but i want to be able to give all dynamic objects a "Navigation Obstacle" Script. Basically the positions get tracked and only the cells which get overlapped by the obstacle should update, and im not sure if a hybrid approach with this would work, or am i mistaking?

haughty zodiac
#

I mean, technically speaking you just need to calculate the intersections and appropriately update the cells that you left and the cells that you entered; If you calculate the cells you touched before and after moving the object you can do this.

beyond that it depends on what you want to do with it and how often they move/update

#

I imagine you need some cell <-> object intersection tests for that to work, this shouldn't be too hard as cells are just AABBs

sacred eagle