Help in Making Path Finder for non Grid based game?

[sanghai45]

Hi community,

I wanted help in making shortest path Finder for non grid based game.

Below is the image attached of which i wanted to do shortest path finding.

There are nodes and each node may link to 5 or 6 nodes.

I have no idea which algorithm will get apply over here so need your help.

THanks guys ~~~

[Eagletalon]

well I dont know much of this kind of coding... but I guess the best trick would be to first get the positions of each node? have that saved and be able to calculate the distance between each node?

then you can start with the current node... the node you want to go to... and compare the combinations of lengths applicable until you get the shortest one...

but without more info I wont be able to say...

[sanghai45]

Thanks dude !!! But what i have thought is that I will be doing Node Search ...using dfs or bfs.

One more thing do you have any idea of how to make tool (levelEditor)
I want to make level editor for this only

I want it to have three buttons CreateNode , Reset Node
Create Node - It will add node in screen
Reset Node - It will reset all the links from the Node

And when the node is created on window if I right click I can set to which Node I want to connect ...

When I am done with making tool I want it to make xml file or text file ?

How to start with this tool ? What should i use ? Any idea?

[Eagletalon]

Well what compiler and libraries are available to you? what are you using too create a UI? OpenGL? DirectX? Qt?

Are you Using Visual C++? Dev C++? a little info goes a long way :)

[sanghai45]

Available libraries with me are of SDL..... I mean UI rendering I will do with the SDL ...
And VisualC++ is what i will be using

[Eagletalon]

Well I guess you could write an entire other program for the editing (which you can open from your main game with a call)

as for the file I think the best bet would be to save to a text file or some kind of encoding thereof... save the co-ordinates of everything and the links between them...

I take it your app will start with some kind of menu? start, load, options, exit etc...

if that is the case also save the name of the text file with an easy-to-read alias in another file (custom levels) or whatever and then access the specified file when requested...

You can then also create the levels you created in the same way and save in a different location or whatever...

In all truth its completely your porogative Im just giving my opinions of how I would do it... you can test alternatives for efficiency and ease of use...

[sanghai45]

Hey Bro!!! I am planning to write tool with cocos2d-x . Here's how I am starting to write my classes as I want to retrieve all data

1. No of nodes
2. No of Connections
3. Array of Nodes
4. Array of ConnectionsLink (How will I retrieve this ? )

consider if my connectionLink is connected to node1 and node 2 then I want information like
1,2
1,3
etc....

struct NodeData{

    float x;
    float y;

};

Class ElementData {

       int NoOfNodes;
       int NoOfConnections;
       NodeData **Nodes;
       // what should i do to get the information of connected links??

};

[Despairy]

DFS wont give u the shortest path
because if node #1 connected to #end node it is one step
but the DFS might go first to #2 ->#3-> ..... ->#end
and this is the only path you will find

try the BFS method , its easy to code . just take a look at a pseudo code somewhere
and figure it out .
hint include <queue> :O!

another hint : each node holds much ... much more information than 2 floats