Sign in to follow this  
npc

Path-finding why always use 2D only to demo your ideas??

Recommended Posts

<rant start> Be honest now in your replies..why isn't there a demonstration anywhere on the internet or in any book ever written on pathfinding done in 3D using DirectX? The conclusions iv'e come to is it's either too difficult to explain,or else the people doing the writing (in books and articles)don't really know themselves or haven't actually put the theory into practice. In honesty,how many times have you read a thesis on this or that,article or book,that tries to explain something,without an actual implementation? without even the most basic of basic examples? how do these people know if something will work(or just leave and expect the reader to work it out by themselves),based on knowledge that is completely different to what is needed(e.g 3D). Is it really that difficult for these book authors or article writers,to write an example in the same style as the DirectX SDK examples or tutorials from NEHE? Here is the warrant for this post/rant on 3D Path-finding: * Been googling for roughly a month for as much information on algos/articles/example source and theory (in particular pathfinding),but AI in general,for use in 3d enviroments. Theory and tutorials on A* and Dijkstra is good,though i have never came across anything in my searches showing them in action using even a simple cube,cone etc in 3D using DirectX,only stupid MFC/GDI apps or 2D tile examples,which i found irrelivent for what i needed. Books iv'e bought or own are similar,these include: *Advanced 3D Programming with DirectX by Peter Walsh,which does explain basic theory on Locomotion/Motorskills,steering,Pattern based AI,Potential functions,Path following/planning and Neural nets. Again,although brief,the example shown is an MFC/GDI app,that wouldleave the most intelligent programmers baffled on how to apply this to a 3d enviroment with 3D characters. * Tricks of the windows game programming -Andre La Mothe - interested in the waypoints chapter- though sadly it is assuming 2D only. * Game programming Gems - OpenGL only(found too difficult to port/apply the ideas in my DirectX applications IMO,not enough OGL knowledge). * AI Techniques - 2D/GDI examples only. * AI Game programming - (is really a book on bot programming for Quake). * Real Time strategy - (A*)Tiles,could not get the ideas working in 3D. On a side-noted question,i found only 2 libs out there for pathfinding.one was a very old lib,with no examples showing how it could be used in a 3D DirectX app,and the other was obviously asking a lot of money,as they did not even have a price for it on their website.Obviously only aimed at the big companies. So what is the answer to get even the most basic pathfinding working in a 3D,DirectX enviroment for an indie game developer? Is there 1 single resource out there at all? Am i the only person who has had this problem or finding this too difficult? or is this a very common rant around here? I would gladly pay a reasonable ammount for a simple 3D DirectX example showing one of the techniques in action if anyone has developed such a demo,if not only to save myself money from the keyboards i keep breaking out of frustration -;) <rant end>

Share this post


Link to post
Share on other sites
Well.. just like Kylotan said, patchfinding in 3d is old good 2d but with one more dimension. :D

And seriously : lets consider A* for 3d. Its the same algorithm, but you have to consider two more neighbour nodes (up and down) for every node. I made only 2d A*, but i recall that i was considering making itd 3d and i found it quite easy.

Share this post


Link to post
Share on other sites
As a pathfinding algorithm needs no graphics whatsoever in order to work, 2d or 3d are equal difficulty. I could make my 2d pathfinder into a 3d one, by adding only a few lines of code (to the 300+ already there)

I could also imagine making a slightly more generic version (perhaps using templating or polymorphism) that would work in n dimensions regardless of n.

The only difference would be that visualisation is much more difficult.

I would recommend that if you're developing a pathfinding algorithm, do it in 2d first, then expand it to 3d once it's working.

Bear in mind, that 2d square, 2d hextile, 3d, 4d etc, are essentially all the same algorithm.

Mark

Share this post


Link to post
Share on other sites
3rd Person shooter/Max Paynish style...the AI/pathfinding doesn't need to be as complex though.

The AI needs similar traits as Resident Evil TM or Alone in the Dark TM.

Fairly basic ideas..Zombies/monsters spawned/respawned on events that are triggered such as when the player enters a room or location,find player...move to his location...Evade etc etc.
Shoot zombie/MPC,zombie falls..gets back up...you get the basic idea.

Need to have path's or(waypoints) for zombies/NPC to wander,go to and find.

The path-finding/navigation is proving to be the most difficult part to get up and running in 3D/directX -;)

Share this post


Link to post
Share on other sites
Does anyone here use the middleware solution PathEngine?

If yes,can you give me a rough(you can be discreet by just saying " a lot! probably out of your price range!")estimate of the licensing prices.Is it reasonable for an indie-project?

I know i could e-mail them,though its normally quite embaressing after they send you all the info first,then tell you its around the 20 grand mark.So i'd rather avoid that if possible.

Share this post


Link to post
Share on other sites
Sorry to not answer the replies(how rude of me-;)

Yes,again..in theory,it would be the same for both 2D graphics and 3D Graphics..but (in practice)if you take a moment to actually try it yourself in a 3D enviroment you'll see that most of that theory goes out the window and (mostly)your left with guessing/trial and error work.

I don't mean that rudely,but have you actually tried any of this yourself in a 3D enviroment? or?

Thanks for your replies though,keep the replies coming,interested to hear the hardcore programmers views/experiences.

Share this post


Link to post
Share on other sites
Game Programming Gems #1 = OpenGL Only...

sorry pipo read the book,worn the -T-shirt and failed with section 3(navigation meshes)of Gems...the theory was very interesting though LOL ;-)

<Edit> before anyone jumps down my throat for my last comment...i will offer 400 US dollars for a succesful port of that demo to DirectX 9(not joking,very serious).

Share this post


Link to post
Share on other sites
nope.But if we all had to re-invent the wheel everytime,we would
all be walking -;)

My offer still stands pipo the clown...are you up to it,or are you too busy? or just blowing steam??

<Edit> your a programmer right? do you want a job actually being payed to any bank account paypal account? for what your saying is easy work...then i must be a fool right? the offer still stands ..or? if your serious please comment more..
if not then i know your just blowing steam -;)

Share this post


Link to post
Share on other sites
From what I've read of A* it should be easily adaptable to 3d tiles. But then again I've never programmed a pathfinder, and my game's map design lends itself to that algorithm.

The problem with 'real life' 3d pathfinding is that it's never generally implimented. I mean what 3d games exist? Space games, where pathfinding is pretty much plotting a line... and FPS games. FPS' though vary so significantly in their implimentation of maps and graphs and movement, that creating a general pathfinding algorithm is challenging.

Most implimentations I've heard of convert their maps into 2d structures by selecting higher branches in their map trees and designating them as waypoints. Then the 3rd dimension is simply added to the distance/weight calculation between the nodes/waypoints. Once the monster/enemy gets to the waypoint, a seperate AI controls their movement and the actual engage/dodge/hide/run logic.

Share this post


Link to post
Share on other sites
Exactly Telastyn...most of the theory goes right out of the top window and your left with a * Lot * of guess work.

Pipo are you still there?

Share this post


Link to post
Share on other sites
Quote:
Original post by npc
Exactly Telastyn...most of the theory goes right out of the top window and your left with a * Lot * of guess work.

Pipo are you still there?


Well, the theory still holds, it just becomes an implimentation dependant problem [ex. How to make this BSP tree look like a mess of nodes and paths] rather than a general one.

As others have said, doing pathfinding in 2d [each node has 2-8 paths from it] to 3d [each node has 3-26 paths from it] to 4d [each node has 4-62? paths from it]... isn't any different to the algorithms.

And a suggestion... Internet routing is the same thing as pathfinding. It though is more arbitrary than game pathfinding, and might give you better examples.

Share this post


Link to post
Share on other sites
npc, first of all. I am not trying to attack or harass you, I'm just suggesting that you (try to) implement it yourself. These forums aren't really for arguing, but for problem solving, so I won't be responding to off-topics.

Why would implementing path-finding in 2D (instead of 3D) would be reinventing the wheel?

Share this post


Link to post
Share on other sites
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.

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.

Pipo,no problem...offer still stands though if you think it is easy work, though,i can tell you that it wouldn't be from experience-;)

Telastyn...
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'.

As you can see,this began as more of a rant out of frustration more than anything else.

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?

Why only use OpenGL? there are enough people that contribute to these books(so called proffessionals in that field) that could take one contributors idea and implement it using the other API,even if the original writer only knew how to program in OGL.

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).

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

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.

Anyone that still says that anything that can be applied such as a theory paper in 2D (and is equally the same (except for the extra dimension(s)using another API is either mislead or blowing steam...and doesn't have any real experience).

Sorry,but i stand by that statement.

Share this post


Link to post
Share on other sites
Your pathfinding algorithm, and indeed any pathfinding algorithm should be completely independant of the rendering API you use. That they both take map data is irrelevant. If your design has the map in some format that makes pathfinding difficult, but rendering easy, that's a design issue, not a problem with perfectly good pathfinding algorithms.





Share this post


Link to post
Share on other sites
I appreciate your insight Telastyn..but it takes us right back to the beginning of my post..why always use 2D only to demo your ideas?

This may be slightly off-of what we are talking about now,but tell me,have you seen any examples in 3D using DirectX?

If there isn't any examples showing their actual implementations
(regarding map formats/grids etc that differ in difficulty)using rendering API's such as DirectX,then can you tell me how is anyone supposed to know how to implement these algo's into realtime-3D-games as apposed to MFC/GDI applications?

I'll check back here in the morning(12:30 here in the UK)
off to sleep now...

Thanks for the input.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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!!!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this