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

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
need help with theory for nodes and adjacency lists
« 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
Code: [Select]
######
#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

Code: [Select]
// 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;
}






Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: need help with theory for nodes and adjacency lists
« Reply #1 on: June 06, 2010, 06:55:55 AM »
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.

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: need help with theory for nodes and adjacency lists
« Reply #2 on: June 06, 2010, 11:32:03 AM »
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.
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #3 on: June 06, 2010, 10:15:54 PM »
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)

Quote
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:
Code: [Select]
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]);
    }
  }
}

« Last Edit: June 06, 2010, 11:04:22 PM by Conal »

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: need help with theory for nodes and adjacency lists
« Reply #4 on: June 07, 2010, 12:34:03 AM »
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?












corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #5 on: June 07, 2010, 01:26:39 AM »
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
« Last Edit: June 07, 2010, 01:49:35 AM by Conal »

Rabiat

  • Rogueliker
  • ***
  • Posts: 88
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #6 on: June 07, 2010, 10:10:33 AM »
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. ;)
« Last Edit: June 07, 2010, 10:13:08 AM by Rabiat »

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #7 on: June 07, 2010, 12:34:14 PM »
Rabiat no you are not making a mistake :) your summation is correct.



ALso if we have a 3*4 grid

Code: [Select]
####
#.  . #
####

do we add cells well nodes to the new suggested tree as follows(Missing diagonals atm)

Code: [Select]

                                    [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 :)
« Last Edit: June 07, 2010, 12:36:05 PM by Conal »

Rabiat

  • Rogueliker
  • ***
  • Posts: 88
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #8 on: June 07, 2010, 02:29:18 PM »
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.

Code: [Select]
#####
#Sab#
#c#d#
#e#T#
#####

Allowing diagonal moves, an exhaustive BFS tree from S to T would be:

Code: [Select]
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:

Code: [Select]
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:

Code: [Select]
S-a-b-d
   -c-e
   -d-b
     -T <--
 -c-a-b
     -d
   -e

In this example, there's just one shortest path:

Code: [Select]
S-a-d-T

I'm still not sure if this is what you're looking for, but I hope it helps.

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #9 on: June 07, 2010, 03:31:07 PM »
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

Rabiat

  • Rogueliker
  • ***
  • Posts: 88
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #10 on: June 07, 2010, 05:29:30 PM »
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.

Code: [Select]
S-a-b-d
   -c-e
   -d-b
     -T
 -c-a-b
     -d
   -e

Zoom it:

Code: [Select]
S-+-a-+-b---d
  |   |
  |   +-c---e
  |   |
  |   +-d-+-b
  |       |
  |       +-T
  |
  +-c-+-a-+-b
      |   |
      |   +-d
      |
      +-e

Kick and flip it:

Code: [Select]
      _____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. ;)

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #11 on: June 08, 2010, 02:11:37 PM »
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]
« Last Edit: June 08, 2010, 04:22:56 PM by Conal »

roguedjack

  • Rogueliker
  • ***
  • Posts: 70
  • Karma: +0/-0
    • View Profile
    • Rogue Survivor blog
    • Email
Re: need help with theory for nodes and adjacency lists
« Reply #12 on: June 08, 2010, 09:07:02 PM »
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.
« Last Edit: June 08, 2010, 09:12:16 PM by roguedjack »

Conal

  • Newcomer
  • Posts: 28
  • Karma: +0/-0
    • View Profile
Re: need help with theory for nodes and adjacency lists
« Reply #13 on: June 08, 2010, 09:30:58 PM »
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?

« Last Edit: June 08, 2010, 09:38:48 PM by Conal »

roguedjack

  • Rogueliker
  • ***
  • Posts: 70
  • Karma: +0/-0
    • View Profile
    • Rogue Survivor blog
    • Email
Re: need help with theory for nodes and adjacency lists
« Reply #14 on: June 09, 2010, 08:05:42 PM »
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:
Code: [Select]
// 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:

Code: [Select]
// 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!
« Last Edit: June 09, 2010, 08:07:29 PM by roguedjack »