Converting 2 dimensional array to node structure

Hello,

I am currently teaching myself C++ and would like to investigate pathfinding more. I have built an environment with a 2 dimensional array, with a structure determining whether there is a wall true/false. The walls are then located appropriated by searching through the array.

I have built a simple algorithm which currently follows the walls always trying to turn left where possible, which ultimately finds the exit -> see video.
YouTube - Fire Simulator 1

For further algorithms e.g depth first it seems I need to convert the array into a node structure, where each cell is a node and has possible edges to connecting nodes north/east/south/west. Any suggestions on the best method for creating this?

It would be also be great to have up to 8 connections allowing for diagonal movement, at this stage I am asking for help with creating the node structure allowing me to investigate the searching algorithms later :)

Many thanks :)

Nodes

If you have created a 2d array representing a map then you already have nodes created, the difference is you now want to store more information at each node location, you could create a 2d array of objects and thus store more properties

More nodes

It depends on your goal, exit a map wit left hand rule u can just test surrounding node status, fastest path to target use astar algorithm, message me 4more or i will add to thread tomorrow

Quote:

Originally Posted by rogster001

It depends on your goal, exit a map wit left hand rule u can just test surrounding node status, fastest path to target use astar algorithm, message me 4more or i will add to thread tomorrow

Its great I`m almost there!
Do you know what extra variables are needed and do you know how the nodes will be connected depending on wall being true or false??

Thanks

nodes

Quote:

do you know how the nodes will be connected depending on wall being true or false

I don't quite follow your thinking here, the nodes i would not consider connected, unless you assign some kind of parent node to them as in astar pathfinding >
the last best step in the path found is made the parent of the new best step in the path, as are all the valid nodes that 'touch' the last best step node.

without this aspect each node is a stand-alone point on the search area, it has an X&Y coordinate, and other properties that determine how you use it, ignore it or otherwise assess its validity in the path.
e.g, node is a wall, not crossable,
or node is an area of more difficult terrain that can still be crossed but at a higher movement cost
in astar pathfinding each node would have other scores assigned to it as part of the algorithm which are used to assess whether it should be chosen as the next best step in the search.
you can represent this with an array of objects as i mentioned but it can be equally done by using a few 2d arrays.

node objects >

Code:

class SearchNodes { public: bool walkstatus; //is it walkable terrain or is it a wall. int Xcoord; int Ycoord; //other properties as required //other properties as required SearchNodes() { walkstatus = true; //initialise variables as objects are created.. int Xcoord = 0; int Ycoord = 0; } }; SearchNodes mynode[10][10]; //you now have an array of 100 nodes each with assigned properties as above.

if you are only ever testing in your program whether or not a node is a wall then a simple 2d array containing a yes / no value would do it, as you arrive at each node you simply test the surrounding 8 nodes for their status.
Given the standard of your example posted i cant see how this is not already basic stuff for you? or have you just added your search routine to someone elses' code or some kind of 3d environment creator?

Hello,

I have now tried to incorporate the depth finding code into my environment. The identifier is floorcells[x][y].exitFinal - if this is set to true the algorithm has found the end point. At this time, we only exist the loop once all edges have been visited. When the search is working correctly, each time the exitFinal cell is found the route will be stored and compared to all available routes for the fastest.

At the moment I have a breakpoint within the exitFinal if statement. This only seems to work if I position the end point close to the starting point. Is my code set up right to reach all cells within the environment?

Many thanks

Code:

while (foundRoute == false) { //once all edges from the start node have been checked the route should have been found if (floorcells[startX][startY].egdesVisted == floorcells[startX][startY].numberOfEdges) { foundRoute = true; } //check if the next edge is the end node if (floorcells[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.X][floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.Y].exitFinal == true) { //foundRoute = true; - each time the final cell is found the route will be transferred to check against alternatives for the fastest route stackArray[stackPos].X = floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.X; stackArray[stackPos].Y = floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.Y; stackPos++; } //if the route has not be found if (foundRoute == false) { //check if there are any more edges to visit from the node if (floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted < floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].numberOfEdges) { //increase stack pointer stackPos++; //set the XY in the stack of the next target nodes stackArray[stackPos].X = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].endNode.X; stackArray[stackPos].Y = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].endNode.Y; stackArray[stackPos].direction = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].direction; //increment edgeds visited variable on node come from floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted++; //increase stack pointer //if all edges have been visited go back down the stack to the previous node } else { //decrement stack pointer stackPos--; } } }

i think you should sort the way that lot looks so its actually a bit more readable before anyone will bother trying to help on this one! Those statements are nuts as a solution, was there no more elegant way to implement this search idea that came to mind? i will scrutinise for sense now but i say again, from what you have posted above compared to your 'YouTube - Fire Simulator 1' example there is a discrepancy.........

sorry but..., i don't want to look anymore!

Hi Rogster007,

There is a graphics api that is handling the 3d environment. the original post was asking for help although I gave it a go, even if it is not elegant.

Thanks for helping! It's a shame we cant have a call to discuss a possible solution

Hello,

I have been working on the code to try and get the search algorithm working correctly. To visualise, the green sphere now follows the route determined by the depth first algorithm, following the instructions defined in the stack. The sphere, checks the next target position and looks at the direction moving accordinly and then repeats.

The problems seems to be that the stack is never decremented, when putting a break point here, the stack is at 1518 which is should not get that high before all edges have been visited on a given node.

In the video below, you can see what happens to the route, the sphere seems to go through all edges available from each node. Can anyone recommend a solution, the data structure is now in place, with each node having the data for the number of edges, number of edges visited, and the X Y start and end details for each edge as well as the direction of the edge.

Any help appreciated :)

Video : YouTube - Fire Simulation 2

Code:

while (foundRoute == false) { //once all edges from the start node have been checked the route should have been found if (floorcells[startX][startY].egdesVisted == floorcells[startX][startY].numberOfEdges) { foundRoute = true; } //check if the next edge is the end node if (floorcells[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.X][floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.Y].exitFinal == true) { //foundRoute = true; - each time the final cell is found the route will be transferred to check against alternatives for the fastest route stackArray[stackPos].X = floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.X; stackArray[stackPos].Y = floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].edges[floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted].endNode.Y; stackPos++; } //if the route has not be found if (foundRoute == false) { //check if there are any more edges to visit from the node if (floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].egdesVisted < floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].numberOfEdges) { //increase stack pointer stackPos++; if (floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].nodeChecked == false) { //set the XY in the stack of the next target nodes stackArray[stackPos].X = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].endNode.X; stackArray[stackPos].Y = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].endNode.Y; stackArray[stackPos].direction = floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].edges[floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted].direction; //increment edgeds visited variable on node come from floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted++; if (floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted == floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].numberOfEdges) { floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].nodeChecked = true; dbColorObject(floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].floorCube,dbRGB(255,0,0)); } //increase stack pointer } else { floorcells[stackArray[stackPos-1].X][stackArray[stackPos-1].Y].egdesVisted++; } //if all edges have been visited go back down the stack to the previous node } else { //if all edges have been viisted set the node to checked floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].nodeChecked = true; //colour the cube red dbColorObject(floorcells[stackArray[stackPos].X][stackArray[stackPos].Y].floorCube,dbRGB(255,0,0)); //decrement stack pointer stackPos--; } } }

you are clearly giving it a really good go yes, its just those really long if statements are so hard to dechipher, that was my only complaint, if you could get them down to a screen width at least would be better, cant a loop be used somewhere instead?