Hi, I was wondering if there is any software that gets the tile map from a 3d scene. I want to program the behaviour of a big number of pedestrians for my school project and I would like to get a fast collision detection and response using 2d grip maps, my problem is that I have already the scenes, I use a ASE loader I wrote to load them , but I don't know how to get a 2d grid from this scene with the collision (walls, and static objects) + characters information. To enter characters information into the array is easy but I don't manage how to handle the collision areas. I have checked a lot of tutorials, but they use random collision maps. I hope you can help me, I have been 3 full days, trying to find out how to do it, but i am really stuck in this part. Thank you very much !!!

It really depends on what exactly you're doing. A fairly general approach would be to create the whole grid, then for each tile look at the corresponding geometry in that tile. If the geometry there would prevent movement across it, mark that tile as being obstructed, non-passable, whatever. For example, if there is a steep slope or a wall in that location, mark the tile as unpassable.

Or perhaps it would be easier to look at the problem from the other direction and iterate over all of the geometry. For each peice of geometry, determine if it would prevent movement, and if so find all the tiles it occupies and mark them accordingly. Either of these methods could be done as a preprocessing step with the resulting information saved into another file.

Another possibility is to write an editor to manually indicate which tiles are passable and which aren't. The simplest way would be to just provide an isometric overhead view of the area with a grid drawn over it, and grid tiles could be colored in transparently to indicate which areas are obstructions.

Your question is a bit unclear. Here's how i understand it:

You have a 3D model of the world
You are wondering how to get a grid representation of that world from the 3D data so you can pathfind through it

yes?

If so, generally the approach is the following:

1) place a "seed point" in your level. this is the place from which the exploration of your world will commence
2) develop a build pipeline that pushes an NPC sized capsule around your world from that seedpoint
3) when the capsule hits another object, or when it hits a slope that is steeper than some pre-tuned value, it knows the current area is unpathable.
4) as it's being pushed around, you note "valid" cells (i.e. cells where it doesn't collide with anything. You can either build your own mesh to represent these valid cells, or you can tag the actualy triangles of the world as valid (depending on your level file makeup and the general design of the project)

At this point you've generated your path network; or at least a starting point for a path network (some apps at this point go into an optimization round of pre-processing to eliminate extraneous polys from the nav mesh).

In short, this is a very complicated process. Perhaps what you want to do is go back to the drawing board about how your levels are designed. The "easy" way to do this is give your level designers a 2D tile-mesh on which they can place buildings, terrain and such. then rather than having to explore for your navmesh, you already have one: placing of buildings or steep terrain invalidates cells on the underlying tile-mesh (this invalidation would be built into your level design tool)

-me

I read that it was possible to get the binary image from the scene
by rendering the scene using an orthographic projection and
storing it in the z-buffer, but it was for opengl,and I am using directx
instead.

I had thought to calculate the bounding box of the scene, and
and use the array just to get the heighs from the scene, if
the height is different from 0 then there would be collision.And I could have
another map for the characters.

Or using coldet to detect collisions against
walls and an array for controlling the characters.
I don't know, what 's more efficient?.

Because my problem is that I must have a big number of people walking around the scene and I need fast collision detection.

One curiosity,does games use this technique of grid-based pahtfinding, or
it is more related to robots?

Thank you very much for answering

There should be a way to use the z-buffer in direct X too.

Try not to get stuck on premature optimization. Get your program working with clearly written code, and if it's not fast enough, then you try to figure out where the bottlenecks are and optimize them.

Using a collision detection library for detecting collisions between characters and the environment should work well. Actually, if you want to stick to the grid for everything, you could use the collision detection library to precalculate which grid cells are collision-free.

Games do sometimes use grid based pathfinding. More advanced engines can use more sophisticated techniques, like using more general graph shapes than a grid, placing navigation nodes in the world and such, but it depends on the needs of the game.

With a large number of characters, one of the bigger challenges is how often paths can be temporarily blocked by other characters. Then you need to decide to wait for the character to get out of the way, or look for another path. You can end up with situations where characters shuffle back and forth trying to get around each other, so a possible solition is to weigh certain directions slightly differently so that for example characters might first try to get around other people by going to their right (relative to the direction they are trying to move).

collision detection and pathfinding are separate systems. Typically you will use the collision detection system to map out the nav mesh. Similarly your agents will be effected by the collision detection system as they try to move around the world.

So, first get collision detection working, then get pathfinding working. Just gaging your experience based on your posts, i'd expect to spend about 2-4 weeks on each system for minimal functionality.

As for what you are calling pathfinding, it's generally split up into 2 systems:

1) Pathfinding - typically done with an A* algorithm to find the route from point A to point B

2) Pathfollowing - also known as locomotion. This applies agent settings (speed, turn radius, etc) to the path and is what harnesses whatever physics system you have in place to actually move the agent along the path found by the Pathfinding system.

-me

Usually if you have easy criteria for movement (no flying, all on flat surfaces, ramps instead of stairs, max slope for allowed movement) you can create a navmesh from your scene mesh almost automatically (an algorithm that traces contiguous facets theat meet the movement criteria). That mesh could then be used as a node network for a pathfinder like A* (simplifying the navmesh might me a bit more difficult -- might be done manually afterwards to speed up A* execution).


Another quick and dirty way (assuming you can get collision up and working) is to manually move around your map writing to a overlaid grid array your location as you move. The finer the grid is the easier you will build an approximation of the available paths. The complexity may be handling the half tile problem where the tiles overlap immpassible edges and you have to filter them out of the allowed set in your grid.

Another method is to manually place waypoints between which you know (visually) there are no movement obstructions and use those points as nodes for A*.

If you intend to have the moving objects not collide (or pass thru each other as Ive seen in at least one recent citybuilder) you will have to do object-to-object collision (easier for the tile grid type solutions).


There was an article in one of the Game Programming Gem books recently (vol6) or maybe was the Game AI Programming Gems (Vol3) that had a solution to the traffic jam problem when using pathfinding by using a modified A* that had a temporal dimension to reserve nodes for time intervals that would be useful for this kind of problem.

Thank you very much, for your help.
You have given me a lot ideas to clear my mind.
Finally I have decided to do it
using the coldet library for the static
objects and the grid system for the moveable characters and I will
use A* for the characters path planning just to control the ones
that are around and the coldet to make sure that that direction is really available. I think that doing it in this way, I will reduce the initial
complexity of checking distances among all actors (o(n^2)), that this is what
I really wanted. I hope it works.

And in the next scenes I draw I will try to use what you told me,
waypoints in the design stage or heigh maps,
I suppose that I will have to use
a map editor don't I?. But first I will try the easiest way.

Thank you again !!!