Working with Terrain

[mohsenz2006]

is there any way to get all he vertices and edges of a terrain in irrlicht?

[CuteAlien]

Moving this thread (FAQ subforum is not for asking questions).
You can get vertices and indices from the IMeshBuffer's which you get from IMesh. Edges are a little more tricky - the easiest solution is maybe to create a ITriangleSelector for that node then you can access the triangle-edges.

[mohsenz2006]

when I read AI books, almost all of them use grid-based graphs with squares of regular sizes. but a terrain's triangles sometimes vary in size. does it make any problem in path-finding?

[CuteAlien]

This stuff is very game-specific - for example I don't think any modern shooter uses a grid-based graph, while you might have that in some strategy-games. Is is also sometimes easier not using the original mesh for pathfinding but an own mesh.

[mohsenz2006]

I'm sorry you said an own mesh? what's that supposed to be?

[CuteAlien]

I mean one mesh used only by the AI. There is often more than one representation of the world - one for visualization, one for physics, one for AI. Sometimes AI uses the same as physics or sometimes all 3 use the same - and sometimes each one uses a mesh for themselves (which are not visible outside the editor). For example if you think it's easier to work with a grid-based mesh then just create one for the AI which approximates the real world geometrie sufficiently - there are games out there doing just that. There will be small corners then which the AI can't reach maybe - but no-one will notice that (although you have to handle the case when the bot is pushed in such a corner - so it has to have a bunch of rules to get out of a corner which is not in it's navigation mesh, for example move a second in random directions, move another second in circles and if still not back in valid movement areas then teleport it there or let it die or something similar). Or maybe you prefer working with a hexagonal map. Or just any kind of polygons which you prefer - for example your algorithm can try to ensure they have all similar sizes (a little tricky). As usual in programming you have lots of possibilities, each has trade-offs, none is perfect and the choice is up to you which one you will try.

edit: Also take a look at AI libraries, there are some out there by now which help you with path-finding. I never used one of those yet, but they can probably make your life a lot easier.

[mohsenz2006]

OK I understand it. But do I need an editor to create a mesh for AI and is it just the so-called navmesh or something different? Or I can do it just by programming? for example I have a terrain in which I want to generate a mesh for AI. could I do it just through coding in Irrlicht?

[randomMesh]

Yes, have a look at irr::scene::IMesh and irr::scene::IMeshBuffer

[smso]

OK I understand it. But do I need an editor to create a mesh for AI and is it just the so-called navmesh or something different? Or I can do it just by programming? for example I have a terrain in which I want to generate a mesh for AI. could I do it just through coding in Irrlicht?

For pathfinding, I used 2 methods:
1. navimesh generated by recastnavigation:
http://code.google.com/p/recastnavigation/

2. waypoints placed manually or automatically by casting vertical rays (for terrain):
http://irrlicht.sourceforge.net/forum/v ... =9&t=46437

Regards,
smso

[CuteAlien]

Nice library smso - recastnavigation even has a zlib license!

[mohsenz2006]

thank you. I downloaded the recastnavigation project. but what if I want to start it from scratch. I mean I like to generate a navigation mash myself. is it really a hard thing to do? what do you suggest me? I have read some books about pathfinding and navigation mesh. They describe everything well but not practically. I just want to know where to start.

[CuteAlien]

Don't know what you mean exactly with "where to start". How to open the editor? ;-)

I think the first step is figuring out exactly what you want your bots to be able to do - moving, jumping, climbing, moving along paths, moving completely free, moving in groups. The movement model in general influences a lot which parts of a map can be reached (slopes for example). And think about what environment looks like - complete 2D (the floor I mean - so no stairs etc), mostly 2D (you have several building levels, but still walk the floor most of the time), nearly free 3D (Unreal Tournament where jumping is nearly flying but you still get back to the floor somtimes) or real 3D (you fly around). Typical level sizes, typical envioronments, is it completely static or can it change slightly (for example walls destroyed, blocked), does it have stairs, latters, movable platforms (avoid them if you can). Or maybe it's even completely dynamic. Another point that matters often is if all bots have the same size or not (for example a large bot will not be able to walk through some small hallways).

And then decide which algorithm you want to try - this is pretty much up to you. The advantages disadvantages are often the first things that come to your mind - like using quadratic blocks for everything is easy to code, but harder to fill the whole level. Using the original mesh makes it hard to figure out the exact area _where_ a bot can walk (for example stairs are looking like small walls depending on how you approach them and many games just use invisible ramps for them).

Not sure if I really helped... maybe try to be more concrete in your question.

[mohsenz2006]

I'm sorry if I wasn't so clear.
simply I would like to program a project like recastnavigation but not so complex. just for a terrain. for more simplicity, I try to keep it static with bots of regular size. even without any obstacles (just for start. I can optimize it later) I'm not sure if I can handle it or not, but I need to try.
for pathfinding in a terrain (with no obstacle), I can simply get the terrain's vertices and implement an A* algorithm. but it need a lot of memory and time to be calculated. until I found out that this can be done through navigation meshes. I have studied them and asked questions and got helped (even by you) but I think I'm still at first position and had no progress.
I hope this time I have clearly demonstrated what I mean. I apologize again.

[CuteAlien]

I still don't know where you are stuck. It's been nearly a decade since I last wrote one, but I think the general way was like:
- Figure out which polygons to use. For example only those which are marked in an editor as walkable. Or some automatic algorithm to find those which can be walked on like for example only those with normals pointing straight upwards (for example every normal with y > 0.7). You might even consider cutting polygons near walls by the radius of the bot to avoid the mesh returns positions which the bot can't reach (because he is too fat to get that close to the wall). But you can also handle those cases later on in movement.
- Figure out the connections between polygons. For example adjacent polygons are usually connected (might not be true if you have for example thin invisible walls between them). So for each polygon you save all connections in some way - for example as a struct containing the next node (another polygon) and the line over which you can cross to reach it (polygon edge in case they are connected at both vertices, but often one edge is shorter/longer so you have to figure out the connected parts). If you make the connection structure a little flexible you can maybe use it later for more advanced connections (like ladders, jumppads, moving platforms). Note that you can have connections either being used in both ways or connections which are one-sided (so you have 2 in them for crossing in both directions - sometimes easier to do it that way). Or maybe use a connection structure than only contains the center of the edge (as maybe only that is needed for routefinding) and figure out the edge-connections later on for optimizing paths (I think I started this way and used whole edges later on for improvements).

Now your polygons are your nodes (but still use an own struct for them which just contains the polygon, it's easier to code) and the connections are the links. You also need a function to check if a position is inside a node (and inside which one). Think about some way to rate the links (for example the distance from the polygon-center to the middle of the line on which you you can cross over to the next polygon). And yes, that's the point where irregular sizes can mess up pathfinding somewhat (maybe there are better ways for rating - remember I didn't do that for years). Well... and now you can run for example A* by giving 2 positions (which find 2 nodes) and then finding the shortest path over the links. Once you found that you can start optimizing the path (as the calculation used the centers of the edges you can now for example check if you can cut corners a little bit).

This was just a very high-level description - the real work is in the details. But maybe it gives you a start.

[smso]

I'm sorry if I wasn't so clear.
simply I would like to program a project like recastnavigation but not so complex. just for a terrain. for more simplicity, I try to keep it static with bots of regular size. even without any otrbstacles (just for start. I can optimize it later) I'm not sure if I can handle it or not, but I need to try.
for pathfinding in a terrain (with no obstacle), I can simply get the terrain's vertices and implement an A* algorithm. but it need a lot of memory and time to be calculated. until I found out that this can be done through navigation meshes. I have studied them and asked questions and got helped (even by you) but I think I'm still at first position and had no progress.
I hope this time I have clearly demonstrated what I mean. I apologize again.

As a first step, compile Recast and run the demo to see what it is capable of doing. Try to understand the 7 steps involved in getting a navimesh from a raw mesh. Then you may want to incorporate Recast in an irrlicht program. Specifically, you have to write codes to convert irr::scene::IMesh to and from rcPolyMesh (and rcPolyMeshDetail) of Recast.

Regards,
smso