Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / Generating a Navigation mesh for a terrain Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
kitt3n

May 19, 2005, 02:36 AM

Hi there,

I'm looking for some way to generate a navigation mesh from a terrain
to do some go/no-go/pathfinding.

I was thinking about sth like "start with 2 nav-triangles and if you
put a tree in the terrain, cut out a (for simplicity) square from the 2
triangles and generate the new nav-mesh"...

Another idea I had was to make a go/no-go bitmap of the terrain in some
resolution and triangulate that into a navimesh.

Did anyone already try to make sth like and have some suggestions on how
to do this? Or maybe there a standard solution/algorithm for this kind of
problem - or a good google-keyword?

Thanks,
Roger

 
[MENTAL]

May 19, 2005, 06:45 AM

Game Programming Gems 1 sums it up.

AI Wisdom 1 makes it faster.

Game Programming Gems 3 also has an article on it, but alas I don't have the book.

 
kitt3n

May 19, 2005, 10:05 AM

Hi,

If you mean article 3.6 (Simplified 3d movement using navigation meshes),
it only mentions you a few rules under "construction" - or did I miss something?
In general the gpg series don't explain on how to actually construct the
triangle-navi-mesh (besides "hand-modelling" which isn't an option in my
specific case) they rather explain on how to use the mesh to do pathfinding.

The ai-wisdom suggestion looks good, it has an article on how to construct
the mesh (and some other interesting topics), so I ordered it :)

 
Brian Legge

May 19, 2005, 01:14 PM

Just curious, why isn't hand construction an option?

 
kitt3n

May 20, 2005, 02:59 AM

For houses I can ask the 3d guys to add navi-data into the .max
model - but we have a huge outdoor terrain (let's say 20x20 km,
in eg 5000 sectors) and I can't ask the level-guys to model a
navimesh for that.

One possible solution is to make a grid for each sector (eg 128x128)
and determine if that position is go/no-go - but it's not nice for
object exactly on the border of a 'tile' and somehow it doesn't seem
really ellegant for a 3d-world

 
Twistofchaos

May 20, 2005, 04:52 AM

Hi,

What are the criteria for a no-go area?

If it is for a player/only few AI's in realtime, (so there isn't a whole lot of go/no-go detecting) you could try to use details of the terrain itself. If it is too steep to climb up, or water, an invisible caracteristic, etc. Then it could work with great accuracy.
But using a bitmap is probably easyer. Tried to calculate..5000 sectors for 20x20km = about 285 meters per sector. Then a 128x128 is probably far too low. (if it's for a walking-game.) But with a higher (x10) resolution it's probably not too noticable or annoying. As long as those edges don't stop the player in a totally blocky shape. :) (Maybe you could use a bigger round shape to detect an edge, or average between bitmappoints somehow.)

Stan

 
kitt3n

May 20, 2005, 06:58 AM

>What are the criteria for a no-go area?
Places where (static) objects are standing, houses, trees, high
mountains (evth with a certain angle) and thinks like that.

I also though about using the detail of the terrain - but we are
trying to seperate logic from rendering (so a gameserver - running
on a different computer - can have a relatively small logic
representation of the world, compared to the huge render-representation).

Btw, you made a really good estimate about our sectorsize, and 128x128
would indeed be too small (The grid idea came to mind because we used
it in our previous game and I just threw in some size :)
Let's say I'd increase the grid-resolution by 4 (so 512x512 with 1 byte
per grid-entry, I'd need 256kb/sector, which gives >1Gb in total...

With a mesh I'd have a huge advantage in desert/grass areas with relatively
few objects (=simple navimesh) - but loose from the grid-solution in #bytes
in densely populated areas.
Which brings me back to the original problem, how to generate it...

Regards

 
Twistofchaos

May 20, 2005, 07:47 AM

>Places where (static) objects are standing, houses, trees, high
>mountains (evth with a certain angle) and thinks like that.

>Let's say I'd increase the grid-resolution by 4 (so 512x512 with 1 byte
>per grid-entry, I'd need 256kb/sector, which gives >1Gb in total...

But it sounds like you only need 1 bit per entry. (go/no-go) So 512x512 of that information is only 32KB. x5000 = 160 MB in total. Better but still a lot.

>I also though about using the detail of the terrain - but we are
>trying to seperate logic from rendering (so a gameserver - running
>on a different computer - can have a relatively small logic
>representation of the world, compared to the huge render-representation).

Then how about those running the game and have all the renderdetail handy, to generate most of it as the gamer goes along. (If he has all details, it doesn't sound like a good idea to store that information extra.)
But then for that gameserver, storing 160MB of bitmaps would probably not be much of a problem. And with 32KB per sector it can load a whole lot of surrounding sectors for hundreds of players in memory at a same time.

Generating such a map is probably really fast for the type of objects you mentioned. You can loop through all the 512x512, but everytime you hit an object of a certain shape, you can eliminate a lot more bits, so you could have a temporary 512x512 bitmap aside that keeps track of what bits and places you already had. And I'm sure you can find other ways to eliminate larger areas at once.

Also to make it seamless you could generate line by line as the player moves of comming-near sectors, instead of all 512x512 at once. (but you also need to load sectors i guess, then you can do at the same time.)


What will the game be about?

Stan




 
kitt3n

May 20, 2005, 12:21 PM

Probably we'll need 2 bits (sth like no-go-half and we'll have 1 state remaining), so 320mb - but still _way_ better than having all renderdata
(I'm guessing that will be 1-2gb's) on the gameserver...
And not to forget compression which might work really well for large
parts of the world (especially desert, grass) - so that might give 30-60% -
and that's pretty okay...

>Then how about those running the game and have all the renderdetail handy,
>to generate most of it as the gamer goes along.
Don't forget the server, running on a different machine - without render-data
should also know the world-logic-data (if only for validation), and
generating it on the client at runtime and sending to the server would
eat network-traffic.

>Generating such a map is probably really fast for the type of objects
>you mentioned.
Generating that bitmap won't be too difficult - The bounding boxes would
give bad results, but I can ask the modellers to make a 'ground-shape' in
each 3d-model which gives the no-go-zone..
Then it's only cutting the bits out - and since the thing will be pre-compiled, it doesn't really matter if it takes some time to generate.

Anyway, I'm going to take a look at ai-wisdom articles on navi-meshes as
soon as I get the books - but at least i've got an alternative :)

>What will the game be about?
It's for the sequel of sacred (an online action-rpg, www.sacred-game.de)

Btw, I noticed you are from Holland - I'm also dutch (I live in
south-limburg). Do you also work in the games-sector?

Regards

 
Twistofchaos

May 23, 2005, 07:25 AM

>>What will the game be about?
>It's for the sequel of sacred (an online action-rpg, www.sacred-game.de)

Wow that looks like a great game, lots of artwork.

>Btw, I noticed you are from Holland - I'm also dutch (I live in
>south-limburg). Do you also work in the games-sector?

I'm from the Gelderland province. (klein dorpje in het land van maas en waal.)

I'm not in the games-sector, but a hobby programmer. (www.geocities.com/tasteofinsanity81/stanspage) But I hope to make myself more known and active in the near future, and see if anything can come out of that.

Groeten
Stan

 
kitt3n

May 25, 2005, 11:54 AM


Okay, got "AI Game Programming Wisdom" today and it contains a helpfull article on how to actually build such a mesh - No sourcecode, but you
can't have everything :)

>Wow that looks like a great game, lots of artwork.
Thanks - the raw artwork is huge in size... We did al kinds of clever
tricks to compress the stuff into package files and keep reasonable
filesizes :)

Good luck getting into the games-sector :)

Groeten
Roger

 
This thread contains 11 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.