long distance pathfinding ... no navmesh or grid.. for large/ terrains

I don't know haw many of you have run into the same problem I have...
There has been no solution for navigation and pathfinding for AI in Unity for massive terrains..

I first ran into this issue a while back, and couldn't really find a solution to it... I read up on every solution I could find and none would work..
I needed pathfinding on a terrain of about 50 sq kilometers. ..everytime I would try to bake a mesh or put down another nav grid, I would be plagued by hangs and freezes... not to mention the occasional crash....there were no solutions... So I decided I would have to work on this..

I am currently working on a theta* solution that will work by making it's own expanding virtual grid at runtime..
Theta* is very similar to A* with a few refinements..
It tends to be quicker in most situations... It tends to find more natural paths, and it is much smoother so even without a smoothing algorithm it helps keep your AI from looking drunk.... and it does most of this by holding onto an additional route and by changing up the parenting of each virtual node...


I'm still in the early stages, but will be testing my algorithm this weekend... I do have another job ( so I can eat and stuff... pay for internet), so this may take a little time...
A few things on the menu though include
weighted paths ... ie roads vs open terrain
line of sight ... cutting off pathfinding if some of the points are visible line of sight, and are open and passable

I'm thinking of checking the terrain for collision by just running a sphere /capsule at the appropriate size through any grid points marked as being possible for the path and just checking for collision triggered

any thought or ideas are welcome... especially for doing dynamic collision testing en route
I 'm probably going to be asking around for some advice on using binary heaps also , since there will be quite large hash-tables to go through... from what I've read that's pretty much a foregone conclusion... I'll just have to start testing without it though..

I'm also going to try to optimize this and put most of the math into another thread .... will have to do a little more research on thread-safe variables... And make sure I stay away from the API with those functions...

wish me luck

 

Hi,
have you considered dividing your calculations in tiles? For example:

1. Divide your terrain in 20x20 tiles
2. When a unit needs to move do a simple A* to check without detail from which of the above tiles the unit must go through
3. After this general A* you will know that your unit will need to go through 8 tiles for example
4. Calculate your new detailed pathfinding only in those 8 tiles instead of 400 that you would need to take into account if you considered the whole map pathable (dont know if thats even a word )

Planetary Annihilation uses a similar technique. They have their planet divided in tiles and only calculate their vector field (they use vector field pathfinding) for the tiles that their unit will pass through.

 

Yes...I have been thinking about something similar... I haven't quite decided how I want to go about it though, because I want to put together a system that will work with any size terrain...even one that is infinite (not too sure if I can achieve this one though)... so the only issue I keep coming to with that is .. if the virtual tile grid is too massive you end up with the same issue the current grid systems have... they choke when you put in too many nodes/ tiles to check..
The only solution I've come up with is to have the virtual grid be dynamic and change on every pathfinding check..
create the nodes as it expands towards the target...
however It might be possible to create a larger dynamic virtual grid of tiles to do the type of check your talking about before running the detailed path and eliminate any expansion if it doesn't pass through one of these nodes....
think i'll put it on the list ...
after I get the detailed path going, I might be able to use it to optimize the algorithm and shorten the loop.

 

Yes, me. Solved with Point Graphs solution from A* Pathfinding Project

 

Sounds like a good idea... I understand you got another job, but just wanted to know when would you be able to make it happen?

 

I had taken a look at that....the main problem I have with that is that I haven't decided if I'm going to use a voxel terrain... if so some of it will be generated at run time... so I really need something that generates itself at run time...

Not too sure... I'm in the last couple of weeks of the project I'm working on now... after that I'll have a little more time...
As I said though I will be started to test the basic algorithm this weekend... hopefully by Sun night I'll have some screenies to show and some preliminary test results

 

Did you looked at Epic solution showcased in Kite demo ?

 

No I haven't seen it... I am currently starting the 24gb download of it ....where I live the bandwidth isn't that great so it might take a day or 2.... but I will be glad to check it out when it's done...
I've dabbled with unreal a little here and there, but it's been a while since I really played around with it , and was unaware of the demo.

 

You can just watch their video event presentation about Kite where they talk about their navmesh dynamic generation ot have some idea without needing to download it.

 

Just watched the event presentation and have to say it was impressive....
The path finding seemed pretty innovative, but not really sure how they implemented it...also I'm not sure if you could use something like that for everything (all types of AI...ie robots, tanks,) or just for creatures)... definitely something I'd like to know more about..
thanks for the sugestion

 

got quite a bit done so far... nothing to show yet

ran across a couple of things that are going to be quite a challenge..
I didn't think it would be that big of a deal to find out what texture was under a given node... to calculate a penalty for terrain type...didn't realize the best information I could find would be almost 5 yrs old!...so
that part will just be added in later...something about having to find the predominate texture in the splatmap and finding just the right cell.... lots of fun so far..

anyway I have the expanding grid of nodes set up... a basic path marker ...shows green or red ..depending if node will work ... I also have the grid adjusted off of the main points and rounding to the nearest whole number... this is so I can cache the results for any given node....later searches can check a few of the values for that node without having to do raycasts to find if a spot is passable .. or recalculate the slope at a node...

just wanted everyone to know i haven't given up on this, and hopefully will have some screenshots by later this week...

 

well this week I've been doing research in to the different ways to sort through the different nodes...

the first thing I learned is that the most common thing used is called a binary heap... I had heard the term before, but had never used one.. binary heaps came about because of a need to have a priority Que... it's pretty much for when you need things to be sorted with a priority... the most common are for say finding the smallest or largest numbers in a list... (there are tons of different ways they can be used...and not just for numbers)... with pathfinding you commonly need to be able to sort through different nodes and decide which has the smallest distance..you don't necessarily need to have every node in the proper order in the list, you just need to know the next smallest each time...
well binary heaps are able to sort very quickly and with a low memory overhead. I, however had a little difficulty wrapping my head around how they work... the programming part... I kept looking at the sort function and didn't quite see it... finally I looked at the whole thing and noticed that the key is in how the numbers are inserted into the list at the top of it.

so now... I'm getting ready to tackle the heap... and I run across a sort function in C# that works in enumerable functions .. IEnumerable.OrderBy ()... can be used in both ascending and descending ... can be used with different priorities and not just for numbers... but for most anything if done properly...
only thing I can't find is if it is slower or faster than binary heaps... I'm thinking probably slower,... but it would be easy to put on a different tr\thread i think...and it requires a lot less programming...
guess Ill just have to throw in a timer to see ... do a few paths each way.. and then decide..

 

rip

 

Binary Heap might be a more efficient way to store the Terrain / Walkable terrain data than a simple Int[,]

I'm attempting Vector Field pathfinding / Goal Based pathfinding for a Tower defence now

since it's Many agents, 1 goal, I can recalculate the paths they should move per grid cell, and store a 2d vector in each grid slot

I'm missing the part that OP already has, I need a flood fill Goal Distance calculation and i'll have my vector fields to move units very quickly

my strategy would fall apart in an RTS setting though because each unit has its own goal

I saw a solution that could work in an RTS sense where the Goal Distance / Vector Field calculation is cached + grouped + only calculated locally / to a depth
then many, many units can run together effectively without each 'agent' calculating anything except for (Unit.transform + Gamefield.vectorField(x,y)*Unit.movementSpeed)

I hope OP didn't rip in peace and is still with us