Hi ,
[Before reading envisage a small test case roguelike on a 6 * 6 grid, it is a 2d array , it has an @ sign a 0,0 which is start point. Next there is the target at 3,3 ]
I had a post up here a while back about certain search algorithms, anyway I had uni stuff to finish so now I am free again.
I went back to the drawing board so to speak and I realised its not setting up a queue fo the breadth first search or having feasible examples to learn how to do the BFS that was the problem in the end but rather my issue is with :
* the concept of a node (It is just to me a struct that stores all information about the on sceen maps INDIVIDUAL cells as well as having a inner struct node *next; pointer to itself
*how to store a 2d array in a linked list where each cell has pointers to each of its neighbours
2d ARRAY
######
#111 1 1#
#111 1 1#
#111 1 1#
#111 1 1#
#111 1 1#
######
# = wall
1= floor also remember the afoementioned start and end locations
Anyway thats a 2d map, through a simple array I managed to procedurally generate a basic oom and doors as well as paths, however now the time has come fo me to get these cells from the array and stored as nodes, so does each node element point to the next? Its just what my test case provided at the end does via linked list node->next is connect
0,0 ->0,1->0,2->0,3->0,4->0,5 (ROW 1 - later I call this level 1 in a test case binary tree)
1,0->1,1->1-2->1,3->1,4->1,5(ROW 2 - later in bintree is level 2 etc)
2,0->2,1->2,2->2,3->2,4->2,5 (OW 3 then bintree lvl 3 later on and so onetc)
Transference to a bin tree yields the following
[Root0,0] lvl0
l r :- l & r are left and right respectively
[A0,1] [B0,2] lvl1
l r l r
[C0,4] [C0,5] [C0,6] [C0,7] lvl2
Although I can add to the bin tree and display it again perfectly I am sure I am going wrong plus the way it searches is from left to right always, that means that any ai would go
0,0->0,1->0,2->0,3->0,4-0,5 then it beams left to (see next row)
1,0! Now continues 1,1 etc until 1,5 then beams left to 2,0
I came to the concusion I need some proper easy set of basic functions to setup a linked list of neighbours which connects to each node, however the way I read about it I will end up with the same problem, I am not sure how to change an aray list into some kind of list that links to all nodes and all nodes links to all and only thier own respective neighbours
I have essentially explained what the test case coede does and where it is wong, I have read a ton of stuff on this but I cannot find an easy to ead procedurally done piece of code as opposed to OO and I would rather avoid another complexity owing to OO or other forms of too high level abstractions that mean I cannot know exactly what is going on throughout
In short
Need help with the practical specifics of how to :
code a non static adjacancy list (linked list maybbe having neighbours)
see how nodes are created and how they link, what pointers they have to where?
How to create a binary tree where every node plus its neighbour are layed out corectly based on the rule each node can have no more than 2 children
Copy and paste the following code over the main file in a visual studio console app , remember it is only a test case, I have had better stuff than this working but I needed to do some independant testing since last time I asked about this a guy was going to help me but needed an example of at least where I am at
// mybfs.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#define MAP_WIDTH 80
#define MAP_HEIGHT 24
int Map[MAP_HEIGHT][MAP_WIDTH]; //y x
struct nod {
int x;
int y;
char str;
bool visited;
struct nod * next;
struct nod * prev;
};
struct tre
{
struct nod * dataptr;
struct tre * left;
struct tre * right;
};
struct que {
struct tre * treePtr;
struct que * next;
};
typedef struct nod node;
typedef struct que queue;
typedef struct tre btree;
typedef struct tre btreeroot;
queue *qstart = NULL; //root
queue *qhead = NULL;
queue *qcurr = NULL;
btree *bintree = NULL;
btree *broot = NULL;
node *thehead = new node;
node *thetail = new node;
node *thecurr = new node;
int tstcount =0;
/*void addToQueue(node *nodetoadd)
{
qhead = new queue;
qhead->current = new node;
qhead->current = nodetoadd;
qhead->next = new queue;
if(qstart == NULL)
{
qstart = new queue;
qstart = qhead;
}
qcurr = new queue;
qcurr = qhead;
//qhead = qhead->next;
}*/
bool EmptyQueue(void)
{
if(qhead == NULL)
{
return true;//true q empty
}
return false;
}
void insertinto(nod *anode, int aflag) //0 root, 1 left, 2 right
{
if(aflag == 0 && bintree == NULL)
{
bintree = new btree;
bintree->left = bintree->right = NULL;
bintree->dataptr = new node;
bintree->dataptr = anode;
broot = new btree;
broot = bintree;
}else if(aflag == 1)
{
bintree->left = new btree;
bintree->left->dataptr = new node;
bintree = bintree->left;
bintree->dataptr=anode;
bintree->left = NULL;
bintree->right = NULL;
}else if(aflag == 2)
{
bintree->right = new btree;
bintree->right->dataptr = new node;
bintree = bintree->right;
bintree->dataptr=anode;
bintree->right = NULL;
bintree->left = NULL;
}
}
void print_cnode(void)
{
if(bintree == NULL)
{
printf("TREE EMPTY");
} else
{
printf("%c",bintree->dataptr->str);
}
}
void print_cnodeb(btree *ele)
{
tstcount++;
if(ele == NULL)
{
//printf("TREE EMPTY");
} else
{
printf("%c",ele->dataptr->str);
}
}
void addQ(btree *ele)
{
if(qhead == NULL)
{
//is first qe
qhead = new queue;
qhead->treePtr = ele;
} else
{
//qhead->next
}
qhead->next = NULL;
}
que * Deque()
{
queue* temp;
temp=qhead;
qhead=qhead->next;
//return temp->treePtr;
return temp;
}
int _tmain(int argc, _TCHAR* argv[])
{
node * curr, * head, *root, *parent, *nstart;
parent = NULL;
curr = NULL;
root = NULL;
nstart = new node;
//parent = new node;
/* parent = new node;
parent->x = 1;
parent->y = 1;
parent->leftn = new node;
parent->rightn = new node;
parent->leftn->x = 0;
parent->rightn->y = 2;*/
int btcount = 0;
head = new node;
curr = new node;
for(int y = 0; y < MAP_HEIGHT; y++)
{
for(int x = 0; x < MAP_WIDTH; x++)
{
if(y == 0 || x == 0 || x % (MAP_WIDTH-1) == 0 || y % (MAP_HEIGHT-1) == 0)
{
Map[y][x] = '#';
}else
{
Map[y][x] = '.';
}
//static loc at 8,8
Map[8][8] = 'G';
Map[1][1] = '@';
//set obstacles
if(x == 3 && y != 4)
{
Map[y][3] = '#';
}
head->x = x;
head->y = y;
head->str = Map[y][x];
head->visited = false;
head->next = new node;
head->next->next = NULL;
node *tmpold = new node;
tmpold = head;
if(y == 0 && x == 0)
{
nstart = head;
}
curr = head;
head = head->next;
head->prev = tmpold;
}
}
for(int y = 0; y < MAP_HEIGHT; y++)
{
for(int x = 0; x < MAP_WIDTH; x++)
{
if(btcount == 0)
{
//setup root in bintree
thehead = nstart;
thetail = thehead;
thecurr = thehead;
insertinto(thehead,0);
btcount++;
//print_cnode();
}else if(btcount % 2 == 0 && thehead->next != NULL) //right
{
thehead = thehead->next;
insertinto(thehead,2);
btcount++;
//print_cnode();
}else if(thehead->next != NULL) //left
{
thehead = thehead->next;
insertinto(thehead,1);
btcount++;
//print_cnode();
}
}
}
btcount = 0;
//now try again printing from broot to end of btree
btree *tstbtHEAD = new btree;
btree *tstbtROOT = new btree;
btree *TNODE = new btree;
btree *TCHILDNODE = new btree;
tstbtROOT = broot;
tstbtHEAD = tstbtROOT;
// print_cnodeb(tstbtHEAD);
btcount =1;
//works well ----this should print you a full map if you want
/*while(tstbtHEAD->right || tstbtHEAD->left != NULL)
{
if(tstbtHEAD->left != NULL)
{
tstbtHEAD = tstbtHEAD->left;
print_cnodeb(tstbtHEAD);
btcount++;
} else if(tstbtHEAD->right != NULL)
{
tstbtHEAD = tstbtHEAD->right;
print_cnodeb(tstbtHEAD);
btcount++;
}
};*/
tstbtHEAD = tstbtROOT;
//stable bintree built so now for breadth first search
//add root to queue very first time
addQ(tstbtHEAD);
//print_cnodeb(tstbtHEAD);
tstbtHEAD->dataptr->visited = true;
//get root node
while(EmptyQueue() == false)
{
//Deque
queue *n = Deque();
if(n->treePtr->dataptr->str == '#')
{
}else
{
n->treePtr->dataptr->str = '@';
}
int i =0;
while(i <9990009)
{
i++;
};
print_cnodeb(n->treePtr);
if(n->treePtr->left != NULL)
{
if(n->treePtr->left->dataptr->visited == false)
{
n->treePtr->left->dataptr->visited =true;
addQ(n->treePtr->left);
}
}
else if(n->treePtr->right != NULL)
{
if(n->treePtr->right->dataptr->visited == false)
{
n->treePtr->right->dataptr->visited = true;
addQ(n->treePtr->right);
}
}
};
//qhead = qhead->next;
//addQ(qhead->treePtr);
/*for(int y = 0; y < MAP_HEIGHT; y++)
{
for(int x = 0; x < MAP_WIDTH; x++)
{
printf("%c",Map[y][x]);
//add nodes to queue
}
}*/
return 0;
}
