Hello !! Previously I have been working with isometric tile-based engines. The pathfinding there is "easy" -> blocked and non blocked tiles. Now I have moved on to 3D engine and I am having problems with the pathfinding. I read some articles that say you allso have to make a "block map" with blocked and non blocked tiles, and then use the "standard" pathfinding algorithm. But how do you guys build such a "block map" ??? For the level I am using a single mesh. Do I have to manually assign blocked and non blocked tiles to that mesh, or are there any better ways to do it ?? Any good articles on that topic out there ??? Thanx a lot!! -- Uros

There is a way to pathfind using the open sectors that you get from BSP partitioning as nodes. I''m not sure how though. Maybe someone else (or google!) can help you if you''re interested in that.

It probably is easier to picture a simple "block map" though. You want to know how to build it? Well, you''ve heard of triangle drawing algorithms that take a triangle rasterize it to a 2d grid of pixels. There''s no reason you can''t do the same thing with a 3d pathfinding grid. Just rasterize all your meshes in 3d to build a voxel grid.

This is my quick response. Someone else can probably help you more with the details of rasterizing triangles to a 3d grid, or, if not, I''ll post back with more later.

I have a paper at home that has the exact answer you are looking for... I''ll try and remember to post the reference tomorrow when I am online again. In the meantime, you might want to try tracking down the following paper:

D.Z. Chen, R.J. Szczerba, J.J., Jr. Uhran. "Planning conditional shortest paths through an unknown environment: a framed-quadtree approach"


Cheers,

Timkin

You don''t REQUIRE a 3d grid of cells... in fact it would be slower the more dense of a grid you created.

What I have considered is finding every "open" space and represent it all with convex shapes that keep track of their neighbors.

The A* algorithm (at least the one that I came up with before learning that someone already came up with it and there was a name for it!) works by making a variable-link tree of non-previously travelled nodes destination-first (until a node is created in the "starting" position, then you simply follow the parent links of each node back to the "destination")

Theoretically it can work with any shape (a grid of squares, triangles, a network of points, or even irregular 3d shapes) -- just as long as you can identify all neighbors for a specific "room" and the distance to the neighbors.

Your solution will be different depending on the possible ways that an entity can travel through the world. If they can only travel along a surface, you can throw out some of the possible "neighbors" that you would NEED if the entity could fly.

Hey !!

Thank you all for help ! Timkin, I was trying to find that article on the net, but I couldn''t get it, so I''d really appreciate it if you could post the paper you are talking about.
Nypyren, your solution seems an interesting one, but honestly, I don''t excactly understand and imagine how to implement it....Could you please tell some more, or direct me to any good article on that topic. TerranFury, I have heard about the rasterizing algorithm. But what do I do once that I have the voxel grid out of 3D level mesh ?? Then I still have to manually work on that grid to tell what is blocked and what is not ?? Or am I wrong ?? Cold you allso point me to any article about the rasterizing algorithm ?

All these solutions sounds quite different, so I intend to do some research on all of them and then decide which to use.

Thanx again !!
--
Uros

quote:Original post by Nypyren

The A* algorithm (at least the one that I came up with before learning that someone already came up with it and there was a name for it!) works by making a variable-link tree of non-previously travelled nodes destination-first (until a node is created in the "starting" position, then you simply follow the parent links of each node back to the "destination")

From your brief description, this is just a variation on the Distance Transform algorithm.


As for the paper, I''m not sure if I still have an electronic copy... I''ll check my archive CDs and let you know.

Timkin

Lol ... I guess I simplified the description to the point of it not being A* anymore...

The biggest difference being that A* is a specific way to optimize the whole process.

[edited by - Nypyren on March 9, 2003 2:58:49 AM]

Let''s say your grid has just 1s and 0s. It''s full of 0s; then you rasterize each triangle with 1s to the grid. The inside of your mesh will still be zeros, but since no path exists through the triangles, that doesn''t matter. Just use your typical A* on the grid. Each node, rather than having 4 neighbors, has 6.

I just ran a Google search. I don''t have Acrobat on this computer, so I can''t read PDFs to check the relevancy of this link, but the title sounds promising: http://www.eccentricvision.nl/papers/Oomes&al1997.pdf
My Google search was "triangle voxelization."