Converting 2 dimensional array to node structure

This is a discussion on Converting 2 dimensional array to node structure within the C++ Programming forums, part of the General Programming Boards category; Hello, I am currently teaching myself C++ and would like to investigate pathfinding more. I have built an environment with ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    8

    Talking 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

  2. #2
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438

    Post 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

  3. #3
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438

    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

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    8

    Smile

    Quote Originally Posted by rogster001 View Post
    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

  5. #5
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438

    nodes

    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?
    Last edited by rogster001; 11-16-2009 at 05:11 AM.

  6. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    8

    Question

    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--;			
    			}
    		}
    	}

  7. #7
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    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.........

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    sorry but..., i don't want to look anymore!

  9. #9
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    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

  10. #10
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    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--;			
    			}
    		}
    }
    Last edited by pawikan; 12-01-2009 at 05:24 PM.

  11. #11
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help Debugging my AVL tree program.
    By Nextstopearth in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 02:48 AM
  2. Help here with qsort!
    By xxxrugby in forum C Programming
    Replies: 11
    Last Post: 02-09-2005, 08:52 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. I need help~~Hash~~THX!
    By freefallin in forum C Programming
    Replies: 5
    Last Post: 04-22-2004, 08:50 AM
  5. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 01:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21