Temple of The Roguelike Forums
Development => Programming => Topic started by: Conal on June 05, 2010, 04:32:26 PM
-
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;
}
-
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
OO is less complex. You should try it sometimes, I mean class programming. You might be surprised. Can't help you with the actual problem though, don't really understand what you are trying to do.
-
Yikes, I might have time to read this post later. And I am with Krice, OO rocks. Also if the standard template classes dont do it for you, you can always expand their capability.
I really hope they still do not teach linked lists in c at uni. I wasted a whole semester on that crap. Lecturers are so backwards.
-
Hey folks,
I have done both OO coding and procedural coding however if I go OO all I have done is added other layers of complexity, e.g having to start faffing about with enumerators and all that jazz. Because the problem is kinda specific I feel it doesnt help to wade in abstractions and then not really know whats going on, especially since I will be using BFS for my AI eventually and am refamiliarizing myself with binary trees. I would rather see this working procedurally. All I need to know really is about my node structure, what should head->next point to if head pointed to cell 0,0? should it point to the next cell e.g 0,1? I have this however it misses stuff out for example if start is 0,0
neighbours are:
0,1
1,1
1,2 (diagonally down right from 0,0 cell)
With OO all these issues still apply, while I appreciate the feedback I really need input from someone who has written nodes and structured them for a beadth first search where there actual map is in an array and then a linked list is used which points to each individual array cells and its neighbours. I need some examples. Even in OO if knowone can do it procedurally but obviously just putting
******This is the crux of what I need, in essence how to prep nodes and pointers for a breadth first search *****
getUnvistedNeighbours() as a method means nothing to me , its the immplementation specifics I require but most of the tutorials just cover the specifics of the search and not how a node is created from an array of cells and then how the linked list of nodes for each cell points to its neighbour
I also will agree to disagree about linked lists being backwards, they are awesome structures and doing it this way I feel at least I know how they are created and used beyond Listref.Add() or somesuch
I will go OO once I get a handle on the AI its just I have started many projects in OO in the past and you end up getting bogged down in OO semantics and at times are working on assumption of stuff working a certain way so I want to gain understanding as much as possible and in the problem area specifically as opposed to fighting with template class syntax amongst a host of OO related and non problem related stuff. Its easier for me to transfer to OO later when I am confident in the knowledge I understand what methods I utilise inside out. (However I want to just focus on getting this problem solved based on the envioment I am using and not get drawn into OO vs procedural debate its silly either way whether one is saying procedural is better or OO. (Pointless)
Lecturers are so backwards
Yes some can be I do agree with this.
.......
I found some java code which I THINK I may be able to create a C++ equivalent of to calculate node neighbours , I figured I would put it here as maybe it can spark discussion or help someone else:
for (int r = 0; r < M; r++) {
for (int c = 0; c < N; c++) {
Node n = nodes[r][c];
List<Node> neighbors = n.neighbors;
if (r > 0) { // has north
neighbors.add(nodes[r-1][c]);
}
if (r < M - 1) { // has south
neighbors.add(nodes[r+1][c]);
}
if (c > 0) { // has west
neighbors.add(nodes[r][c-1]);
}
if (c < N - 1) { // has east
neighbors.add(nodes[r][c+1]);
}
}
}
-
I only commented about OO because your post was too long and I didn't quite understand what it was you wanted.
And your code would be MUCH easier for the rest of us to read if you had, say, a node class.
Let me get this straight, you are pre-calculating node neighbors for each node that will be later used for a BFSs? And you want to know how to find the valid neighbors?
-
Yes thats it, there are other areas I need to refine as well but I need to calculate node neighbours first and foremost.
Btw I just as of 10 mins ago setup a linked list of neighbours, basically each node struct has a pointer to a neighbours struct
*node is a pointer to node
node has a *next pointer
node has a *neighbours pointer
neighbours is a struct
neighbours has a *next pointer
so in essence what I THINK I have working is that each array grid cell which is pointed from a node has its neighbours pointed to by node->neighbours
so element n in node points to a sub linked list of neighbours for that single node
I have succesfully printed out all the neighbours string values e.g '#' and or . but although my progam doesnt error I will not know for sure whether I have solved the problem or not until tommorow when I try to test it more times. Either way any suggestions are welcome and thanks for the replies
ow one other thing , well things I should say to make my code a bit easier to follow is mention the fact that I do the following: (I did things this round about way to prove I could use certain structures/ data structures)
1: fill a 2d array with a square boundry roguelike wall #
2: use moduolous operator on the array to input 1 vertical wall
3: place an @ in the array
4. place a mob in the aray which is the @s destination
5:read each array cell into a linked list, each linked list element is a node which holds a cell
6: new code I have on my person now for each node adds a neighbours pointer which points to the FIRST neighbour in a linked list of neighbours
7: Try to get a handle on binary trees so I take all my linked node pointers(e.g the main node linked list which contains respective neioghbour pointers sub linked lists) and add them to a binary tree,
6: display the binary tree (This is just the output which is identical to whats in the 2d array except its a copy thats pointers in a linked list)
NOte before adding the binary tree and mish mashing many concepts well suffice to say the code done before I asked this question, e.g the binary tree linked list and 2d array I have printed out to make sure it worked
no problem with regards to what you are saying about OO its just having coded a reasonable amount using both ways I honestly believe that once I get this problem solved I could make either procedural code or OO code and both as readable , its just I have been experimenting with a good few concepts in that code above . I will probably go OO its just I feel I really need to get a handle on breadth first search in a way that means I understand it personally. I realise OO is just as good its just I went OO with a good few projects and for the first time I go procedural for a roguelike I feel its forced me to undestand things a little better, I base this on the fact I got my first randomlly generated room,s working and just got so much further this time. It is probably just because I am getting more practice at coding and OO has nothing to do with it , who knows :)
Anothe aspect is if it was c# or java I was using I would 100% go OO but C++ OO well its kinda more messy in my eyes hehe, I need more C++ OO practice me thinks
Finally yes, just looked over my code, taking an objective look at it and yes I agree its not exactly going to win any competitions , especially not readability :D
-
Hi Conal,
You're trying to implement BFS for pathfinding on a 2D map, right?
It's probably easier to use a general N-ary tree in stead of a binary tree for search space, since a node (=location) can have up to eight child nodes (=neighbouring locations). To build the tree, add the source location as the root node, then add its neighbours as child nodes. For each leaf node, add its neighbours as child nodes, skipping nodes that already appear as a superior node (these represent loops). Keep adding tiers to the tree until the last tier contains at least one leaf representing the target location ('target node'). Any path from the root node to any target node is a shortest path. Pick a random target node, and backtrace to the root node to get the path.
If that's what you're trying to do, and if I'm not making some stupid mistake. ;)
-
Rabiat no you are not making a mistake :) your summation is correct.
ALso if we have a 3*4 grid
####
#. . #
####
do we add cells well nodes to the new suggested tree as follows(Missing diagonals atm)
[source 0,0]
leaf [0,1]
leaf [0,2] [1,1]
[0,3] [1,0] [1,2] [2,1] [0,1] //left right down up neighbours of 1,1
is my above partial tree along the right track? if so I may see whats needed to get this working a more elegant way. (Btw whethe what I am saying is right or wrong massive thanks for looking at what I have done and giving some advice , is just once I get over this hurdle I will see some visual stuff happening and be able to create a rough game, I know when I have a shell game to work with I will never stiop coding :)
-
I don't think I understand your example. Just to be sure, I'd like to say that there is a difference between the map structure itself and the search space for pathfinding. The map structure can be a 2D array, a linked list, or anything which lets you determine adjacent locations. Building it should be fairly easy.
Once you have the map structure, you can construct a search space, which could be a tree. It's not necessary to put wall tiles in the search tree, since it's impossible for a character to move there. In your example, you would only need to build a tree containing [1,1] and [1,2], which isn't very clarifying.
Here's another example. I've marked the source (S) and target (T) locations, and all other 'floor' locations with letters, to avoid having to write coordinate pairs.
#####
#Sab#
#c#d#
#e#T#
#####
Allowing diagonal moves, an exhaustive BFS tree from S to T would be:
S-a-S*
-b-a*
-d-a*
-b*
-T
-c-S*
-a*
-e-c*
-d-a*
-b-a*
-d*
-T
-c-S*
-a-S*
-b-a*
-d-a*
-b*
-T
-c*
-d-a*
-b-a*
-d*
-T
-e-c*
I.e. from S, you can move to a and c; from a, you can move to S, b, c, or d; from c, you can move to S, a, or e; and so on. Nodes marked with an asterisk are loops, i.e. the leaf node is equal to one of its superior nodes. You don't have to add these to the search tree. Omitting the loops leaves you with:
S-a-b-d-T
-c-e
-d-b
-T
-c-a-b-d-T
-d-b
-T
-e
There's also no need to build the tree exhaustively. You can stop building the tree if T was added as a leaf node in the last iteration. In this case the depth of the tree is equal to the length of the path, so all shortest paths must be known. In this case, T is added after the fourth iteration:
S-a-b-d
-c-e
-d-b
-T <--
-c-a-b
-d
-e
In this example, there's just one shortest path:
S-a-d-T
I'm still not sure if this is what you're looking for, but I hope it helps.
-
Its a differet way of achiving what I have nearly managed to achieve now however please keep this up. To start with I didnt follow the format of your tree but after studying it I think I do now and you also refer to specific paths through your tree which is exactly one of the things I need to be able to do so please keep your post and diagrams up :) I was up verry late last nigh so just going to get some sleep but I will definatly use information from this topic, I wont ask any more questions until I can manipulate n -arr trees and can add remove and scan for a dest from a source.
Thanks a heap for your help, pun not intended :D
-
No problem. Good luck, and let us know if you got it to work.
Sorry about the formatting, it's just that these things are a nightmare to do in clear text.
S-a-b-d
-c-e
-d-b
-T
-c-a-b
-d
-e
Zoom it:
S-+-a-+-b---d
| |
| +-c---e
| |
| +-d-+-b
| |
| +-T
|
+-c-+-a-+-b
| |
| +-d
|
+-e
Kick and flip it:
_____S______
/ \
___a___ c
/ | \ / \
b c d a e
| | / \ / \
d e b T b d
Doing this manually for a complete Angband level is left as an exercise for the reader. ;)
-
No problem :)
I am away to do some coding now so I will let you folks no in a couple of days. No worrys about the formatting although your latest addition really helps even more.
I have had grief about my own formatting before but as you say it is indeed a knightmare to format certain stuff in a forum post, still the meaning is conveyed and that is what counts.
I did binary trees in college waaay back but this is the first time I have used them in a project along with linked lists and I believe once I up my coding skill just a little more and get my binary trees layed out well I will have my ai done as I more or less understand the searches. After AI my project will have some life and I dont think I will have any motivation issues when I get to that point; I see at this time a hurdle overcome and soon after actually being able to play my game. (I imagine that must be a great place to be as a developer)
Btw It seems like my previous way of a linked list then a neighbours list within each node MAY have worked, I am about to create a new project and try things the way suggested however I ran a heap of test data into a file and I included the LAST portion of that test data
I did all this and not the whole file because people may have taken it as spam even though it is not, anyway here it is :)
IT starts from X[67] Y[23[ , coord base just means the curent element hasneighbour [someneighbou, has neighbour[some nighbour] etc
Coordbase: X[67], Y[23] Has neigh: X[67], Y[22]
Has neigh: X[67], Y[24]
Has neigh: X[66], Y[23]
Has neigh: X[68], Y[23]
Coordbase: X[68], Y[23] Has neigh: X[68], Y[22]
Has neigh: X[68], Y[24]
Has neigh: X[67], Y[23]
Has neigh: X[69], Y[23]
Coordbase: X[69], Y[23] Has neigh: X[69], Y[22]
Has neigh: X[69], Y[24]
Has neigh: X[68], Y[23]
Has neigh: X[70], Y[23]
Coordbase: X[70], Y[23] Has neigh: X[70], Y[22]
Has neigh: X[70], Y[24]
Has neigh: X[69], Y[23]
Has neigh: X[71], Y[23]
Coordbase: X[71], Y[23] Has neigh: X[71], Y[22]
Has neigh: X[71], Y[24]
Has neigh: X[70], Y[23]
Has neigh: X[72], Y[23]
Coordbase: X[72], Y[23] Has neigh: X[72], Y[22]
Has neigh: X[72], Y[24]
Has neigh: X[71], Y[23]
Has neigh: X[73], Y[23]
Coordbase: X[73], Y[23] Has neigh: X[73], Y[22]
Has neigh: X[73], Y[24]
Has neigh: X[72], Y[23]
Has neigh: X[74], Y[23]
Coordbase: X[74], Y[23] Has neigh: X[74], Y[22]
Has neigh: X[74], Y[24]
Has neigh: X[73], Y[23]
Has neigh: X[75], Y[23]
Coordbase: X[75], Y[23] Has neigh: X[75], Y[22]
Has neigh: X[75], Y[24]
Has neigh: X[74], Y[23]
Has neigh: X[76], Y[23]
Coordbase: X[76], Y[23] Has neigh: X[76], Y[22]
Has neigh: X[76], Y[24]
Has neigh: X[75], Y[23]
Has neigh: X[77], Y[23]
Coordbase: X[77], Y[23] Has neigh: X[77], Y[22]
Has neigh: X[77], Y[24]
Has neigh: X[76], Y[23]
Has neigh: X[78], Y[23]
Coordbase: X[78], Y[23] Has neigh: X[78], Y[22]
Has neigh: X[78], Y[24]
Has neigh: X[77], Y[23]
Has neigh: X[79], Y[23]
Coordbase: X[79], Y[23] Has neigh: X[79], Y[22]
Has neigh: X[79], Y[24]
Has neigh: X[78], Y[23]
-
I think you should look at graphs not binary trees.
Using graphs to express a N->N relationship is the natural way to do it.
If you don't know about graphs, but know about trees, think about graphs as more generic trees where:
- a node as X leafs. (in binary trees X = 2 : one parent = 2 childs max).
- a leaf can be linked from Y nodes (in binary trees Y = 1, one child = 1 parent max).
In your case,
Node = "a map cell"
Link = "is adjacent to".
and there is no parent vs child notion (all nodes are both parents and children of each other = symetric/adirectional graphs or whatever the term is in English)
http://en.wikipedia.org/wiki/Graph_%28mathematics%29
Not sure why you would need this kind of structure though on top of your 2d array.
-
Thanks for your addition, it helps,
I can print out nighbours with just linked list structures however each node points to an independant version of its neighbours i.e things arent interlinked as I should have them so it looks like I am going to have to do a rewrite but I am unsure of how to do trees that are not binary trees but rather every node has x neighbours , for instance in a binary tree we do bintree->left then bintree->right so could I just change each tree element to have say
Struct bintree
{
struct bintree *current
struct bintree *neighbourNORTH; //or should these be struct nodes?
struct bintree *neighbourNE;
struct bintree *neighbourEAST;
struct bintree *neighbourSE;
struct bintree *neighbourSOUTH;
struct bintree *neighbourSW;
struct bintree *neighbourWEST;
struct bintree *neighbourNW;
};
struct bintree *btree;
Btw I just realised now that I know the neighbou coords I could adjust the array direcly and re display to screen
I have been doing alot of testing today I just need to make some headway in certain areas pertaining to structure since theres alot of ways and additionally alot of pitfalls :)
In theory what would be the best steps
Read into 2d array a map;
display 2d array map
simulate an ai move to some location
do bfs
As it stands I read the array cells into a linked list of nodes where each node is a cell , I can printf every cells neighbours but updating the actual search path so I can show temporarly the oder of steps taken is kinda tricky because of how I made neighbourrs an independent structure that gets pointed tio by a pointer in the node struct
Im also looking for c examples of how to do TREES that have more than 2 branches well any amount, I believe these are narray trees?
-
For N-ary trees, just use a "list of nodes" as children.
Something like that...
(Code will not work right away, you'll have to use typedefs + forward declaration. Its been a long time since I wrote pure C :P)
For the tree:
// a tree
struct Tree_t
{
// root of the tree, null if tree is empty.
struct TreeNode_t *m_Root;
};
// 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;
};
and for list of nodes:
// a list of nodes.
struct ListOfTreeNode_t
{
// entry into the list, null if list is empty.
struct ListElement_t* m_FirstElement;
};
// 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;
};
I think you are also confusing different data and structures:
- a tree is not a node.
- a node in the search space (where the BFS is at a particular time) is not a node on the map (a cell).
It will be clearer if you start thinking into terms of algorithm and worry about the implementation later.
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.
Remember google is your friend to find sample code and algorithms ;)
Good luck and happy coding!
-
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
-
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.