Author Topic: need help with theory for nodes and adjacency lists  (Read 19657 times)

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #15 on: June 10, 2010, 01:17:40 AM »
Hey :)

Last post is really really useful reply! Some of what you say that I am confusing a node with a tree(Then again maybe I was lol, I just figured each tree element was a node or a pointer to a list of nodes, the tree is what I am most new at but I am getting there - narray codee has really helped since I believe I can do the tree at least on arbitary data, fitting it into neighbours + the seach is the final hurdle I am tustling with though as my neigbours code atm is having problems) is perhaps a bit of but this is bang on:

Quote
- a node in the search space (where the BFS is at a particular time) is not a node on the map (a cell).

I was gradually comming toward this realization and was incorrectly mixing display of the screen with order of search. I totally agree with what you said though and the code provided is exactly what I was looking for.

I think I am close, i honestly believe its just down to a few silly things and I can have this completed.

.......

I just started doing this the last 2 days and I am at the stage where I fall over after a couple of iterations of checking neighbours, I debugged and it looks like a pointer is pointing to gabage at some point so going to fix tommrow

Quote
Just image you already have magically implemented all your data structures, but are missing the procedures/functions to make your pathfinding work.
Write your BFS algorithm using these magic data structures. Then write the data structures.


I am determined to do this so rather than sticking to one project I am making like multiple mini test case type pojects as I google and get forum and book info and uit is helping

Feels like so near but yet so far :)

Huge thanks all!

edit..................

I have done some work today based on the replies. Anyway I know that this is not corect but it does at least run in essence whats happening is I have 1 tree root node whicj connects to a linked list

so node at 0,0 is root (Btw Im just trying to create a map of cells plus neighbours at this time not bfs and I am making some mistakes

anyway fom root it has 4 children : , East, south, north and west

so Tree node root points to list elements , East, north, south and west nodes , each list node points to their espective child nodes so I have one root and a massive list

I want 1 root, a list of 4 child nodes and then another tree node which points to its child nodes, in short I am unsure if I have done this correctly although I think all data is now stored, anyway I submit the full coding, if anyone feels like verifying it works or is wrong in a certain way then copy and paste the below code into a visual studio console c++ project in your main file and you can witeness it running

btw I must stress I am not at the stage I am doing bfs , I realised its the neighbours and whole adjency of the map setup I am botching so I took it back a level and I know once I see a working example of this part I can do the rest, th is part is where all botch ups have eminated from anyway heres the code :)

I wouldnt usually do this but I have read like hell and I cannot find source code that shows how to setup the map then lists how I am trying to do so

Code: [Select]
#define MWIDTH 9
#define MHEIGHT 9

// a tree
struct Tree_t
{
// root of the tree, null if tree is empty.
struct TreeNode_t *m_Root;
};

struct ListOfTreeNode_t
{
// entry into the list, null if list is empty.
struct ListElement_t* m_FirstElement;
};
typedef struct NodeData_t
{
int x;
int y;
char str;

}cell;
// a tree node
struct TreeNode_t
{
// node can have any number of children, from zero to a lot.
// so we use a list.
// if no children, the list is empty.
// no pointer as we own the list.
struct ListOfTreeNode_t m_Children;

// node specific data, like position, value whatever... defined by you somewhere else.
struct NodeData_t m_Data;
};

// a list of nodes.


// an element in the list.
struct ListElement_t
{
// the node being hold there.
// its a pointer because the node might be in many more lists, we do not own it.
struct TreeNode_t* m_Element;
// next element in the list, null if end of list.
struct ListElement_t* m_Next;
};


cell acell[MHEIGHT][MWIDTH];
int iter = 0;
struct TreeNode_t *tnode = new TreeNode_t;
struct Tree_t *troot = new Tree_t;
struct ListElement_t *lsthead = new ListElement_t;


void initMap(void)
{

for(int y=0; y<MHEIGHT; y++)
{
for(int x=0; x<MWIDTH; x++)
{
if(y == 0 || x == 0 || x % (MWIDTH-1) == 0 || y % (MHEIGHT-1) == 0)
{
acell[y][x].str = '#';



}else
{
acell[y][x].str = '.';
}

acell[y][x].x = x;
acell[y][x].y = y;


}

}




}

void setupMapTree(TreeNode_t *tn,int ax,int ay)
{


if(tn == NULL)
{
//first time so create a new tree node
tn = new TreeNode_t;

tn->m_Children.m_FirstElement = NULL;
tn->m_Data = acell[ay][ax];
troot->m_Root = tn;
}

for(int y = 0; y < MHEIGHT; y++)
{
for(int x = 0; x < MWIDTH; x++)
{
if(x < MWIDTH-1)
{
//has east

if(tn->m_Children.m_FirstElement == NULL)
{
tn->m_Children.m_FirstElement = new ListElement_t;
                    tn->m_Children.m_FirstElement->m_Element = new TreeNode_t;

tn->m_Children.m_FirstElement->m_Element->m_Data = acell[y][x];
lsthead = tn->m_Children.m_FirstElement;



}
else
{


//we should have a next element thats free
lsthead->m_Next = new ListElement_t;
                    lsthead = lsthead->m_Next;
lsthead->m_Element = new TreeNode_t;
     lsthead->m_Element->m_Data = acell[y][x];
                  


}
}

if(y > 0)
{
//has north

lsthead->m_Next = new ListElement_t;
                    lsthead = lsthead->m_Next;
lsthead->m_Element = new TreeNode_t;
     lsthead->m_Element->m_Data = acell[y][x];
}

if(y < MHEIGHT-1)
{
//has south

lsthead->m_Next = new ListElement_t;
lsthead = lsthead->m_Next;
lsthead->m_Element = new TreeNode_t;
     lsthead->m_Element->m_Data = acell[y][x];
}

if(x > 0)
{
//has west
   lsthead->m_Next = new ListElement_t;
                    lsthead = lsthead->m_Next;
lsthead->m_Element = new TreeNode_t;
     lsthead->m_Element->m_Data = acell[y][x];
}

}
}

}

void showScreen(void)
{
for(int y=0; y<MHEIGHT; y++)
{
for(int x=0; x<MWIDTH; x++)
{
printf("%c",acell[y][x].str);

}

}


}

void addtoQueue(void)
{
}

void getUnvisitedNeighbours(void)
{
}
int _tmain(int argc, _TCHAR* argv[])
{
initMap();
showScreen();
setupMapTree(NULL,0,0);
return 0;
}

note resize your console window, I made the console window rediculously small for testing purposes until I get this neighbours in a map setup corectly, I am almost certain I understand A* as well as BFs but I dont 100% follow how to get neighbous setup and checked , its kinda frustrating , still Im learning I guess :)
 

.....
Its alot to expect someone to check my code but even if someone could point me in the direction of source code that immplements a breadth first search as well as setting up nodes and their neighours iin a TREE and in C then I would be grreatful. I checked some source but could not find anything that is using core c, however I will have a proper look tommorow for something that uses c and has non library made TREES and then a bfs
« Last Edit: June 10, 2010, 10:15:51 PM by Conal »

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #16 on: June 16, 2010, 05:06:58 PM »
I have replied instead of edited so that people who are considering bfs can see some of the stupid mistakes I made along the way.

Anyway pretty much every piece of advice given in this thread played a part in helping me to get something like bfs working

In essence I know have a testcase where by the ai finds its way to the player, the only situation which is not catered for is if the ai mob ends up in a dead end and evey node around it is visited, at least I think that ones not covered, I know how to rectify though I believe which I will do tommrow

I ditched the binary tree and the guy who debated OO with me can have a laugh to himself because I ended up after all this taking his advice and used 2 vectors, an openlist vector of points(nodes) and a closed list(I will be adding functionality to this so that the algoithm wont ever get stuck)

anyway the vector meant I didnt hav to worry so much about memory management and I am really happy with the progress made all be it my solution is no where near as cool as a TREE


I was making the mistake of trying to have it so the ai had eveything like flood fill mapped.


Really pleased and I got some good help of the RGRD chat room but aparently I am a sneak professional, thats no biggie, its bull but no problem its just Im guessing I may get banned if people are implying I am some how sneaking their code, I learned to declare a vector via the chat room if that constitutes a professional I think I better come out off education! Yes my code is really leet aand Im a secret microsoft employee ROFL

Anyway thanks those of you who utilise some common on a daily basis and who have helped.