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:
- 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
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
#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
