Pathfinding - 'Dungeon' to 'Node list'

Mecharius · Post by **Mecharius** » Thu Jul 27, 2006 1:18 pm

Hi guys,
As my first major project in irrlicht I'm trying to make a basic FPS. I'm trying to steer clear of things like STL, and AI libraries as I think I'll learn more that way! I have made some data structures to start with (lists, queues etc) and have now moved on to some basic pathfinding.

The maps are sort of simple dungeons. To make pathfinding more efficient I thought I'd reduce the map to a list of edges, representing corridors, and nodes representing intersections and rooms. This is just for the pathfinding, and I'll still have the ok3 file for the map...This image should give you an idea of what I have in mind - red lines are edges, blue circles are nodes.

I am reluctant to hard code the nodes and edges in, or write them out 'manually' as I think this would make level development more difficult later. Is there a way I can get a list of nodes and edges from a pk3 file - a gtkRadiant script or some other method?

Somebody mentioned something about a blender script in another forum post but I was hoping to use gtkRadiant. I've done a forum search (e.g.) and I'm aware that irrWizard can help, but I would like to try implementing this myself...

Thanks for your help!

Acki · Post by **Acki** » Thu Jul 27, 2006 5:12 pm

Hmmm, maybe this could help you ???
http://irrlicht.sourceforge.net/phpBB2/ ... hp?t=14183

Well, the path finding demo uses waypoints that are hard coded, but maybe you could use this code...

Mecharius · Post by **Mecharius** » Fri Jul 28, 2006 2:10 am

Hi Acki,
Thanks for that, I'll have a look

I'm fine with writing a pathfinding algorithm - I've done an A* one for a game I wrote in VB.NET (

) ages ago... I was going to do Dijkstra's this time just for something different, and A* if it was too slow. But the small number of nodes should mean that pathfinding is relatvely quick.

But yeah, I'd like a way to get an XML list of nodes and edges from the .map or .pk3 file, without just writing them out.

Thanks for your help!

JP · Post by JP » Fri Jul 28, 2006 12:52 pm

Hey, this sounds similar to what i did last year for my dissertation at Uni. I was creating some intelligent agents for a basic FPS framework i designed.

What i did was to represent the dungeons in a grid style and then i limited the agents to only being able to move N, E, S or W to the next cell (though this could be improved to free movement i'm sure) and then i did path finding using breadth first search, iterative deepening depth first search and a best first search.

If it sounds like i might be of any use to you then let me know and maybe i can help!

Mecharius · Post by **Mecharius** » Fri Jul 28, 2006 1:56 pm

Thanks JP, sounds interesting... One question - how did you represent the dungeon as a grid style? Did you just read from the map mesh, or did you have some other method?

As I've mentioned above I can handle the pathfinding algorithm itself with no probs, its just a matter of getting the data from the map file. I could just record the world location at each node and write it manually into an XML file but I was hoping somebody could suggest a slightly more intelligent method...

Thanks for your reply

JP · Post by JP » Fri Jul 28, 2006 3:03 pm

So you're actually using pre-built maps? like quake ones? I used a random maze generator to make the grid representation and then rendered that in 3D using wall, floor and ceiling meshes as building blocks.

I also then wanted my agents to be able to map the dungeon themselves (originally i just gave them the grid representation as a map so they could find their way around, but i thought them mapping it themselves would be better). To do that i sent them running around and at each grid square they would cast out rays in all directions and detect where the walls were and then map the dungeon in that manner. Not sure if that's the sort of thing you're trying to do and whether that would help... I've no idea how good a method it is, but it worked great for me!

Mecharius · Post by **Mecharius** » Fri Jul 28, 2006 4:36 pm

Yeah, I think I'll use quake style maps - as I said its my first major project in irrlicht - I've only made 2d VB games before

I've got quake-style maps working for a simple test game I made.

Your approach sounds pretty interesting - particularly the self mapping bit, did you get it working in the end?

It looks like I'll just have to manually zoom around the map and sort out my own XML file with nodes and edges. I can then load it in to the app and use the graph that it creates for large scale pathfinding. Its not like i'll be creating hundreds of maps

JP · Post by JP » Fri Jul 28, 2006 9:50 pm

Yeah the mapping worked perfectly, unfortunately i couldnt use it in my final version as it caused problems with the AI pathfinding when the map was incomplete.... Made the agents act really stupid, so i just included it as an extra demo.