Quote:Original post by npc
why isn't there a demonstration
anywhere on the internet or in any book ever written on pathfinding done in 3D using DirectX?

I'm replying more to the fact that you mentioned in the thread about trying to get a A* solution in 3d.

I would guess that A* pathfinding is too obtuse and contrived for 3d worlds. Most 3d worlds are not set up on a block/cell basis. I guess A* pathfinding is great for maybe a voxel engine but in regular polygon worlds it's just not worth the effort. By extension it wouldn't be worth it to write an 3D A* app in dx.

Instead of using A* a better idea would be to use Waypoints like unreal tournament uses. Although I don't know if you can find waypoint demo applications in DX. I'd imagine one would be easy to write up or convert though.

Also another reason A* in 3 dimensions doesn't show up is because most games allow the player movement only along 2 dimensions attached to a surface. Like a terrain or platform. Most games that allow for 3d movement don't need A* pathfinding because they can move right to where they want to go and only have to avoid obstacles like space shooters. Even Descent 3 I beleive used way points for the AI of their robots. To have a AI have to go through an A* algorithm to find a path would be far too complicated rather then just doing a simple way point algorithm.

I'm sure you can find a waypoint or obstacle avoidence application on the net that's written in 3d or easy to convert.

Anyways, good luck searching for your 3d dx pathfinding app.

~Wave

Quote:Nugget5555... Lol ok then,which car do you want?
gamedev used to be about learning...time is more important than learning 'inside-out'something that is mostly the same/common in every 3D game.

Then you could also state that because cooling systems are common in cars, a mechanic wouldn't have to know how they work. Someone who makes chairs, first has to learn how to make them.

Quote:I have nothing against learning...I do however,have something against wasting my time caused by people that haven't applied something to real world problems before they take credit for being so called 'great' game programmers or intelligent AI programmers in the AI field,or being classed as a great book author/article writer.

By now it should be clear that pathfinding in 3D really isn't very common. As said, the so-called 3D world often really only needs 2D pathfinding.

Quote:Well,that is what this post is really all about..
Having a theory about something without showing a real implementation is almost totally useless.I have theories about things all the time,but that doesn't mean they will be of any use in the 'real world'.Well,that is what this post is really all about..

Why shouldn't implementing A* in 3D be possible?

Quote:Take popular books like gems.Why not have the main article(the theory)then have both a simple implementation in DirectX and Open GL.Would that be really that difficult for them to do?

Because you should be able to understand the OpenGL code. After I've done some OpenGL (NEHE :P) I find it quite easy to read Direct3D code in another book I have. Isn't that the same the other way around?

Quote:Everyone who is anyone knows that everything is moving more and more away from OpenGL and DirectX is becoming the overall leader of the 2 API's(PC PLATFORM mainly).

Everything that is /not/ Windows or XBox does not have DirectX support. (Too bad though that Windows has by far the largerst marget share.) Besides that, there are many reasons to choose OpenGL.

Quote:Why use OpenGL? because it was much easier to implement that idea using that API(yes i have looked at that source (Section 3)).

Pathfinding easyer to implement in OpenGL? Now that's what I call bullshit. You only use the 3D API to display the result, not the process.

Quote:Which makes the idea(s) almost irrelivent if your using a more modern API such as DirectX.Those ideas are/were difficult to apply using the latest DirectX API.

Suggesting that OpenGL is not modern is just weird. The fact that OpenGL is not as feature bloated as Direct3D doesn't make it modern or not.

Please stop flaming towards OpenGL. Both OpenGL ánd Direct3D are great libraries, one more suitable for some tasks than the other, and the other way around.

Also, another reason to stop arguing about Direct3D/OpenGL is that the 3D API really does not matter in this case.

hey npc ... can u a bit elucidate exactly what is that you finding difficult to port from opengl to d3d (i am referring to the gems example)..??In my view,pathfinding is totally separate from the api u use!Correct me if I am wrong!!!

The thread was started in the DirectX forum,as i am implementing path-finding using the DirectX API,although i'm hearing the same thing here again and again,that the implementation details/API i'm using shouldn't/don't matter.

I would have posted it in the MFC/GDI section,as that seems to be the choice to demo a lot of AI..though there isn't one -;)

Well,(just in case i'm not being clear)it isn't as straight
forward/clean cut as most of you are making it out to be.

Unless youv'e tried things yourselves(put into practice)you can't possibly understand what i'm talking about.

Before dropping by to your friendly forums,iv'e been all over the net,and if you think what i have written in this 1 thread is strange,weird or total bullshit(as Sijmen mentioned that he thinks i'm talking)you should look around other forums,especially some of the AI websites,and you'll see that my complaints/questions about similar things such as books on AI etc,have been almost identical to what i have written here on many forums.

Sijmen..if that was true,there wouldn't be middleware solutions such as PathEngine,read what thomas(the creator) wrote over at flipcode when he first announced/showed it for the first time to the community,he stated every game he's ever worked on,that the pathfinding system was almost the same/identical,which lead him to develop such a solution,other middleware exists to save the developer time,and there is no need to understand the full 'under the hood' details to be able to use it.

You make it sound like its a weird programmer'honour' type of thing for using middleware or not coding something bare bones completely from scratch.

This is why sometimes open source projects can be good for other developers.

As for your comment about "You should understand the OpenGl code"I don't want to use the OpenGL Api for this project,that's just my choice.

I was simply saying that the way most of you talk around here,when someone writes a book (or an animation system-;)using directX specific helpers etc,you all scream.."I want to know how to do the same with Open GL"or "i want to write it completely from scratch".

Well then,wouldn't that same rule apply to the gem's books? or does this rule only apply to jim adams's books,and can be changed when you feel it needs to be?I said Gems would be more popular overall,for developers using both API's,if there were implementations for both Api's.

Maybe that simple concept,is too weird to get your head around,i don't know.

<Pathfinding easyer to implement in OpenGL? Now that's what I call bullshit.

err..was talking about a demo in section 3 in the gems book.
which was more of a quick 'hack' than a real path finding solution,but that isn't important now.

<Please stop flaming towards OpenGL.

LOL;-) amazing how you interpreted that i am now flaming OpenGL.
I didn't even know that...please don't try to put words into my mouth.

<Also, another reason to stop arguing about Direct3D/OpenGL is

Nobody is arguing about D3D/OGL.This is a public forum on the internet for game developers to err (Try to)..discuss/help/and solve problems,Just because i don't agree with what one person has said,or have a different take on it,doesn't mean i'm starting an argument with anyone.Don't take offence...its only game development,it doesn't really bother me that most of you here are dissagreeing with me,in fact sometimes it can be quite funny/entertaining to read -;)


Anyway,a friend of mine from a uni in essex,read this thread last night,and after sending me an amusing e-mail(cheers Gaz) he passedon a link to a DX8 demo source code with basic 3D pathfinding for me to study.So..Problem solved.

If anyone is interested in a DX8 specific implementation for 3D
Pathfinding with 3D characters,let me know,and i'll send you the link.

An API-specific AI algorithm.... that's amusing.

I used Djistra's pathfinding algorithm in my last project, taken from the awesome tutorials avaliabe here on Gamedev. It was a freaking Shockwave3D game, and it uses a custom programming language. If the theory could be used in such different context, why would it require magic powers to work under DirectX? Unless you are looking for copy and paste code (and all your whining gives me this impression, sorry), I see no problems.

Also Djistra's scaled naturally intro 3D, since it's waypoint-based, and not grid-based like A*. This means you don't have to check closed nodes. You have a map of unevenly distributed nodes, and each node contains a list of the neighbor nodes, and the cost to reach that node. The cost is usually the plain distance between the nodes, and this alone works in full 3D space (AI entities can move freely in any direction), since the nodes can be placed in 3D space with no problems.

It's also easy to do it in 3D where gravity applies, by using the height differences between the nodes as a cost multiplier, so if a neighbor node is too high, the cost to reach it becomes massive and the AI agents will automatically use the stair to go up there (if you place nodes there too), instead of trying to climb the wall.

Jim, this should actually be moved to Article Requests.

npc: as I (and several other posters) pointed out, path-finding has absolutely nothing whatsoever to do with graphics APIs, and if your code is even remotely sane, your pathfinding will not touch a graphics API with a barge pole.

The fact that you want an example that has 3d graphics reflects lack of imagination on your part.

A* and Dijkstra are extremely similar, you will find that to convert one into the other is just a couple of lines (actually A* is slightly more complicated, take those few extra lines away and it changes into Dijkstra's)

A* works for arbitrary graphs, as does Dijkstra, it's just that for tile-based games those graphs have tiles for nodes. It could be the same in 3d too, but it's unlikely in a 3d game which isn't tile based. More likely you would create waypoints and link them in a graph.

Graphs of course are an abstract mathematical notion and know nothing of how many dimensions they are in.

Think of something with isometric 3d multi-level tile-based graphics, like "UFO:Enemy unknown" or perhaps Syndicate, and you will see how a tile-based 3d pathfinder like A* could work. However in these games most units cannot fly, so they are largely limited to the ground, with the exception of stairs and lifts.

For something where there is genuinely total freedom like "Descent", I'd go for a graph of interconnected nodes with waypoints. I'm pretty sure that's what Descent uses for the AI of its bots (Actually in Descent 1 the bots didn't move around much, in Descent 2 there was a little bot which followed the player around helping out)

Mark

I actually did path-finding (in 2D, of course [grin]) for my honours thesis. From the background reading I did then, I can tell you that usually 3 or higher dimensional pathfinding is *not* done with a grid based approach. You might just get 3D A* or something working, if you've got a small world and you don't mind using a coarse grid, but complexity of path-finding is usually exponential in the number of dimensions. Most higher-dimensional pathfinding (especially when you're talking about multi-jointed robots, where you're pathfinding in 6, 8, or 12D space) uses probabilistic roadmaps. A set of waypoints, and safe paths between them, is precomputed, giving a 'pretty good' approximation in a non-geological timespan.

Come to think of it, I seem to remember an article which was boasting about optimal 3D path planning between polygonal obstacles in only single-exponential time (as opposed to the previously-best algorithm which was double exponential, e^(e^num_verts) )

To recap: It's bitchin' hard. That's why no-one does it. :)

So why always use 2D only to demo your ideas?? [lol]