• Create Account

# Path-finding why always use 2D only to demo your ideas??

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

87 replies to this topic

### #41markr  Crossbones+   -  Reputation: 1608

Like
0Likes
Like

Posted 09 July 2004 - 12:03 AM

Why don't you create another tutorial, called

"Casting iron using a wooden spoon"

Mark

### #42npc  Members   -  Reputation: 100

Like
0Likes
Like

Posted 09 July 2004 - 12:31 AM

Though i'll be working on the path-finding tutorial first -:)

### #43fup  Members   -  Reputation: 463

Like
0Likes
Like

Posted 09 July 2004 - 01:10 AM

There is no difference whatsoever between searching a graph for a path in 2D or 3D (or any amount of dimensions). If you do not understand why there is no difference then you do not understand graphs or graph search algorithms sufficiently.

Authors of books and tutorials of AI related techniques tend to use two dimensions because the majority of AI techniques work with any number of dimensions. There's no need to explain something specifically in 3D when it's much easier and quicker to code demos and draw illustrations for examples given in 2D. This also makes it much easier for the reader to understand a technique. Almost all AI techniques scale up to 3D (or more) with no or little effort (especially pathfinding)

I suggest you buy something like "Algorithms in C++: Part 5, Graph Algorithms" by Robert Sedgewick, which will give you a solid understanding of the problem you wish to solve.

[EDIT]: sorry Jiia, I've only just noticed you said just about the same thing.

### #44papalazaru  Crossbones+   -  Reputation: 1802

Like
0Likes
Like

Posted 09 July 2004 - 02:06 AM

For FPS, path finding in 3D or 2D is similar. You get the polygons of your environment marked as floor, generate waypionts (automatically or not), and inter-link them. What's the difference with 2D?

You just have to be careful with not connecting waypoints that are out of reach (like on another floor). Then do a A* on the waypoint graph from where you are, voila.

that's how we do it anyway. The main problem is basically generating waypoints and linking them, and that's not particularly tricky. It's just time consuming.

For tile-based, I don't see the difficulty either.

The problem would be is you want to use another system, like a delaunay trianglulation of the floor, or some hierarchical polygon-based structure, to give a more 'fuzzy' path for the NPCs, but then again, Again, it's just building the graph that's the problem, after that, it's the usual A* process.

### #45 Jiia   Banned   -  Reputation: 592

Like
0Likes
Like

Posted 09 July 2004 - 02:08 AM

Quote:
 Original post by npci think your confusing/repeating the statements of others in this thread without any real experience in this matter..actual implementation using one -;)

Main reason I replied was to explain why most demos are probably written in 2D. But then I noticed a few other people were on the same 2D->3D conversion trip. Graphically, 2D and 3D AI is exactly the same.

No, I've not yet written a graphical 3D game which used pathfinding. But most of my 2D games which used it had 3 deminsions (x,y,z), and multiple levels stacked over each other. The same coordinate system can be used to make Max Payne. Hence, the same pathfinding can also be used.

### #46npc  Members   -  Reputation: 100

Like
0Likes
Like

Posted 09 July 2004 - 03:58 AM

fup,no offence,but your book is very misleading to anyone searching or looking to buy a book that will teach them how to * implement * basic AI into their game projects such as path-finding.

And if i remember correctly,several months ago,there was someone requesting/having problems getting some of the techniques in your book implemented into a real 3D project.I think you told him(or someone else) mentioned that they would see a small demo soon,which never did happen.(unless there's one now,and i'm wrong).

< when it's much easier and quicker to code demos and draw illustrations for examples given in 2D.

Of course it is Lol:-)Its also easier to avoid the actual 'getting these techniques working in a real 3D game project' altogether.

Sorry,but as someone else here as already mentioned,you can talk,talk and talk about something until your blue in the face...unless you have something solid(such as a real game demo) to back it up with...then it doesn't matter.

I suggest that if you write another book with a title that has "Games" in it,have some real * 3D *game demo's with it -:)
DirectX and OpenGL are what most people use...not GDI/MFC.

Original post by Pipo DeClown:
This should actually be moved to Article Requests.

You can move this thread(as mentioned,my problem is solved) to
Article Requests if you would like...though i doubt anyone will write a full one covering real 3D path-finding anytime soon -:) like most of the difficult article requests iv'e seen,that never do get written or are forgotton about.

olii...you make it sound very easy.I don't suppose you have actually written a tutorial covering Path-finding in a 3D enviroment?

I think i remember reading something you wrote on collision detection though in 2D?

Ok..lets take a step back(about 44 relies ago)...

Other than the demo sources i have...has anyone here written an article,tutorial or demo on path-finding for use in a real 3D Game enviroment?

Show me 1 single resource on the net,that either covers this subject sufficently,or has demo source,showing a real implementation.

Do any of you know of any book recently written(within a few years)that has demo's for their books in a real 3D game enviroment?

Yes? or No?

<Edit>
Apart from gems..
and the suggestion i made,about having implementation in both OpenGL and DirectX.
Please stick to/don't avoid the questions
(AND DON'T TAKE OFFENCE!! ITS ONLY A DISCUSSION ABOUT GAMEDEV-:)

[Edited by - npc on July 9, 2004 10:58:42 AM]

### #47 Jiia   Banned   -  Reputation: 592

Like
0Likes
Like

Posted 09 July 2004 - 04:46 AM

You're missing the point, npc. It doesn't matter if your game is 3D. You can use a 2D pathfinding algorithm in a 3D game. Everyone knows this. So why would anyone spend extra time complicating a tutorial by adding 3D characters and animation to their demo?

Which part of the pathfinding do you not understand? Which part changes when you try to use it in your 3D world? If you haven't tried it, then why are you even here?

By the way, oliii has practically mastered 3D collision detection. I suggest looking into his stuff if you need help with that as well. Hell, just do a search for his name in the forums, and you've got better than a book.

### #48fup  Members   -  Reputation: 463

Like
0Likes
Like

Posted 09 July 2004 - 05:07 AM

I think you need to search internally for why you are failing to overcome your problem rather than externally. You seem to have great difficulty adapting the techniques you see in books and tutorials to slightly different scenarios.

"And if i remember correctly,several months ago,there was someone requesting/having problems getting some of the techniques in your book implemented into a real 3D project.I think you told him(or someone else) mentioned that they would see a small demo soon,which never did happen.(unless there's one now,and i'm wrong)."

You remember incorrectly.

"fup,no offence,but your book is very misleading to anyone searching or looking to buy a book that will teach them how to * implement * basic AI into their game projects such as path-finding."

I agree the title is misleading. Unfortunately that was a decision made by my publisher way into the project and I had no say in the matter. I wanted the title to be "Neural Networks and Genetic Algorithms for Game Developers" but LaMothe would have non of it.

My next book covers more traditional game AI techniques (but I still don't use DX or OpenGL... what for?). I recommend you don't buy it though as your IQ level (judging by your responses to the helpful advice people have taken their time to give you in this thread) does not seem to be high enough to comprehend the information contained within.

### #49npc  Members   -  Reputation: 100

Like
0Likes
Like

Posted 09 July 2004 - 06:23 AM

"My next book covers more traditional game AI techniques (but I still don't use DX or OpenGL... what for?). I recommend you don't buy it though as your IQ level (judging by your responses to the helpful advice people have taken their time to give you in this thread) does not seem to be high enough to comprehend the information contained within."

Oh dear [wow] i think someone has taken it to heart,sorry i should have coated my reply in suger for you first-:)

If your judging my responses...then if you use some common sense (that is sense that doesn't require qualifications)
you'll see that most of what i have written,is clear,to the point,that any average intelligent person can make sense of and understand the problem(s) and the original rant about books etc,other people have even explained how difficult these problems can be in detail.

If you can't understand after some mixed 40 odd (some faily long)replies about what the point of this post is,then i can't help you...there is no courses/tutorials that i know of..on "how to gain common-sense" [headshake]

Btw..of course i appreciate everone's replies/help and opinions
that took the time to reply..the problem is..i didn't seem to be get very far did i?,apart from a few helpful replies..and seemed just going round in circles explaining why i was writing a post like this[smile]

### #50Nuget5555  Members   -  Reputation: 396

Like
0Likes
Like

Posted 09 July 2004 - 06:40 AM

Just out of completely dumb-founded curiosity...

what kind of game are you creating that requires 3d path finding, and why wont 2d path finding work?

### #51Telastyn  Crossbones+   -  Reputation: 3624

Like
0Likes
Like

Posted 09 July 2004 - 06:42 AM

No offense, but if 20 people post that you don't know what the hell you're talking about, and you say the 20 people don't know what they're talking about, odds are the 20 people are right.

Hell, I should probably take the 2 hours it'll take to impliment an arbitrary dimension version of A* just so you can bitch about it not being "3D"...

### #52 Jiia   Banned   -  Reputation: 592

Like
0Likes
Like

Posted 09 July 2004 - 07:01 AM

Can I just respond one more time here. I would like to clarify the difference between 2D and 3D pathfinding.

First of all, it has nothing to do with your graphics API. The only difference between them is another direction you can move in. Most games DO NOT NEED this. Max Payne is a good example. Characters do not fly around in that game. So the bots do not need 3D pathfinding. They use the ground + steps + ladders + elevators to move around. Therefore, you plot waypoint grids down on the ground, each one having information about how much effort it takes to reach each neighbor point around it. Then it's as simple as following the most effortless path to your goal.

### #53npc  Members   -  Reputation: 100

Like
0Likes
Like

Posted 09 July 2004 - 09:49 AM

Telastyn - No offence taken.. now..

"but if 20 people post that you don't know what the hell you're talking about, and you say the 20 people don't know what they're talking about, odds are the 20 people are right".

Telastyn..let me just tell you something.

We can trade/match wit in this thread for the next few days if it amuses a lot you..(its quite funny to see how shallow some of the people around here i once admired and thought great,to see how ridiculous some of them are being with their responses).. Though so far,i haven't yet seen 'anything that special'around here [cool]

Let me know guys,when you want to talk serious and 'get in-depth' about what problems i have faced (and still trying to solve) regarding path-finding and the project i am working on.

[Edited by - npc on July 9, 2004 4:49:57 PM]

### #54Pipo DeClown  Members   -  Reputation: 804

Like
0Likes
Like

Posted 09 July 2004 - 10:21 AM

Quote:
 Original post by TelastynNo offense, but if 20 people post that you don't know what the hell you're talking about, and you say the 20 people don't know what they're talking about, odds are the 20 people are right.

I said something off-topic.[/edit]

[Edited by - Pipo DeClown on July 12, 2004 2:21:16 PM]
I'm not back. I'm just visiting.

### #55Telastyn  Crossbones+   -  Reputation: 3624

Like
0Likes
Like

Posted 09 July 2004 - 10:40 AM

Quote:
Original post by Pipo DeClown
Quote:
 Original post by TelastynNo offense, but if 20 people post that you don't know what the hell you're talking about, and you say the 20 people don't know what they're talking about, odds are the 20 people are right.

Not always true.. Evolution is fake, but so many people believe it.

/me chuckles. Troll much?

Anyways, back on topic, I've doodled up that pathfinder I was talking about [my first!]

I should be able to post the code tonight, hopefully with a tutorial sort of thing.

### #56Silex  Members   -  Reputation: 140

Like
0Likes
Like

Posted 09 July 2004 - 12:10 PM

I would recommend against posting code. Odds are this guy is just trying to get someone to do his work for him, and if you give him code you'd just be playing into his little plan.

That or he's really as thick as he appears...in which case you should post an exe without any source just to shut him up.

[Edited by - Silex on July 9, 2004 6:10:06 PM]

### #57npc  Members   -  Reputation: 100

Like
0Likes
Like

Posted 09 July 2004 - 12:46 PM

All depends how many of the posters are idiots [lol]

Silex...that's a good way of * Not * backing all this bull-sh*it i've had to read for a couple of days now...what is he embarressed i may laugh at it?? or what?? Lol-;)

### #58Nuget5555  Members   -  Reputation: 396

Like
0Likes
Like

Posted 09 July 2004 - 12:54 PM

npc you didn't answer? What kind of game requires 3d path finding???

### #59 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 09 July 2004 - 02:50 PM

Quote:
 Original post by SilexI would recommend against posting code. Odds are this guy is just trying to get someone to do his work for him, and if you give him code you'd just be playing into his little plan. That or he's really as thick as he appears...in which case you should post an exe without any source just to shut him up.

I was going to write a long post dissecting and responding to his original argument but you've said pretty much everything I was going to say. =)

At least he's got his "pacifier" now... (code given to him by a friend implementing the stuff he was asking for)

### #60Telastyn  Crossbones+   -  Reputation: 3624

Like
0Likes
Like

Posted 09 July 2004 - 03:22 PM

Okie dokie.

This is a tutorial that came about due to some debate about pathfinding algorithms and their applicability to multiple dimensions and rendering APIs.

BACKGROUND

I am a fairly novice progammer. I've programmed in C for about 4 years, and C++ for 1 year. This is my first attempt at a pathfinding implimentation. This implimentation uses the A* algorithm. If you're unfamiliar with the algorithm, please ask google to familiarize you with it. The tutorial is meant as a code sample, and assumes you know a bit about the algorithm used.

The context of this code is for my current game project. Some of the structures used are not shown/listed. I will at least try to go over the most common ones here, and will answer questions about others in greater detail.

The most commonly used is the vine class. I am not familiar with the STL, and was in need of a variable length array class. The vine class is defined as:

struct vine{	types	type;	void	*data;	vine	*next;	vine	*prev;		// functions};

types is an enumeration of all the various data types used in the project. This allows for mixed types to reside in the same vine. The vine class also has some other functions which are primarily used to add or remove members from the linked list.

The other important details of this implimentation are centered around the way I store my map information.

The map is formed by 2 main classes. A class for individual nodes where things may exist, and a class for paths that objects may use to travel between these nodes. For turn based strategy games, the nodes may be tiles, or planets. The paths simply implicit by virtue of one tile being next to another, or perhaps they're star lanes connecting planets together. For 3D games, they're likely waypoints, or nodes of a spatial tree. The paths would just be true or not true should a wall be in the way, or a locked door blocks movement.

For my game, the nodes are hexes, and the paths are just different ways to travel between them. Your game will be different, but the base idea of nodes and paths is pretty much required for this algorithm.

The relevant class definition for my node class:

class hexinfo{public:        hextypes        hextype;        coord           xyz;        hexinfo         *next;        vine		*paths;        // snip}*hexes;

hextypes is an enumeration of all the various land types the map can be [grasslands, ocean, mountain, etc...]
coord is simply a int[3] typedef. The coordinates are used only for reference. A unit cannot travel to an adjacent hex unless there is a path. The coordinates exist to allow for a quick judge of distance without counting paths.
hexes is the global list of nodes in the map; in the hexinfo constructor, each hex is added to that list.
paths is a variable length array containing all of the paths from [or to] this hex.

Speaking of paths; the relevant class definition for my path class:

class path{public:	class hexinfo   *from;        class hexinfo   *to;                    // for most, this will be irrelevant,                                                 //  as the path will be bidirectional.        class pathdef   *ptype;        // snip};

Very simple. Pointers to the nodes which the path connects, and a pointer to a path definition class.

Pathdefs are meant to be the rules of a path. What units can use them, how much movement points the path uses, things like that.

Now to the definition:

class pathdef{public:        char            name[32];        void            (*travel)(class unitinfo *,path *);        int             (*traveltime)(class unitinfo *,path *);        pathdef         *next;        // snip}*pathdefs=0;

The name is just an ID. Something to describe the pathdef as unique from others.
travel is a function pointer that takes a unit, and moves it along the path. Since it's a function pointer, I can code up whatever machinations I like to govern the movement of a unit.
traveltime is a function pointer that takes a unit, and returns the AP [action points] it would take to travel that path.
pathdefs is the global linked list of definitions.

Please stop here, and read back through if you're not terribly clear on the general concepts. A vine in my code is just an STL vector to most people. hexinfo is a node. path is a path. pathdef is the rules governing that path.

PATHFINDING IMPLIMENTATION

#define         MOEPF_HASHSIZE  29#define         MOEPF_XWEIGHT   1#define         MOEPF_YWEIGHT   1#define         MOEPF_ZWEIGHT   5#define         MOEPF_APPERHEX  2struct astarinfo{        hexinfo         *hex;        unsigned int    steps;  // steps from the start.        unsigned int    left;   // estimated distance from the end.        unsigned int    ocu;    // open|closed. 0==closed 1==open 2==unset};class pfhash{private:        vine *pftbl[MOEPF_HASHSIZE];public:        pfhash(){};        ~pfhash();        void            init(hexinfo *f,hexinfo *t);        astarinfo       *add(hexinfo *inhex);        astarinfo       *ptrtoasi(hexinfo *inhex);        astarinfo       *getbest();};astarinfo       *pfhash::add(hexinfo *inhex){//// add inhex to a asi struct, and then put that into the hashtable.//astarinfo       *asiptr;unsigned int    x;asiptr=new astarinfo;asiptr->hex=inhex;asiptr->steps=0;asiptr->left=0;asiptr->ocu=2;// TODO: make a better hashing functionx=(unsigned long)inhex%MOEPF_HASHSIZE;(new vine(ASI,asiptr))->top(&pftbl[x]);return(asiptr);}void            pfhash::init(hexinfo *f, hexinfo *t){//// loop through the tiles and add each to the hashtable.//hexinfo         *hptr;int             co[3];int             endco[3];unsigned int    a;astarinfo       *asiptr;// INIT TABLE COLUMNSfor (a=0;a<MOEPF_HASHSIZE;a++){        pftbl[a]=0;}endco=t->xyz;for (hptr=hexes;hptr;hptr=hptr->next){        co=hptr->xyz;        asiptr=this->add(hptr);        // create a guess about how long it should take to get from this hex to the end.        asiptr->left= MOEPF_APPERHEX * (                        MOEPF_XWEIGHT * abs (co[0]-endco[0]) +                        MOEPF_YWEIGHT * abs (co[1]-endco[1]) +                        MOEPF_ZWEIGHT * abs (co[2]-endco[2])                        );        if (hptr==f){                // if this hex is the start                //  make it open;                asiptr->ocu=1;                asiptr->steps=1;        }}}astarinfo               *pfhash::ptrtoasi(hexinfo *inhex){//// hexptr in, asiptr out.//vine            *v;unsigned int    x;x=(unsigned long)inhex%MOEPF_HASHSIZE;if (!pftbl[x]){        return (0);}for (v=pftbl[x];v;v=v->next){        if (((astarinfo *)v->data)->hex==inhex){                return ((astarinfo *)v->data);        }}return(0);}astarinfo               *pfhash::getbest(){//// return the asiptr which contains the current "best" route.//unsigned int    x;vine            *v;astarinfo       *asiptr=0;astarinfo       *bestasi=0;unsigned long   bestint;// TODO: use MAXULONG or whatever the max actually is.bestint=70000;for (x=0;x<MOEPF_HASHSIZE;x++){        if (pftbl[x]){                for (v=pftbl[x];v;v=v->next){                        asiptr=(astarinfo *)v->data;                        if (asiptr->ocu==1){                                if (bestint> asiptr->steps + asiptr->left){                                        bestint=asiptr->steps + asiptr->left;                                        bestasi=asiptr;                                }                        }                }        }}return(bestasi);}pfhash::~pfhash(){//// nuke everything;//unsigned int    x;vine            *v;astarinfo       *asiptr;for (x=0;x<MOEPF_HASHSIZE;x++){        if (pftbl[x]){                for (v=pftbl[x];v;v=v->next){                        asiptr=(astarinfo *)v->data;                        delete asiptr;                }                pftbl[x]->nuke(&pftbl[x]);        }}}vine    *asitohex(vine *invine){//// convert invine [ASI] to outvine [HEX]//vine    *v;vine    *outvine=0;astarinfo       *asiptr;if (!invine){return (0);}for (v=invine;v;v=v->next){        asiptr=(astarinfo *)v->data;        (new vine(HEX,asiptr->hex))->bottom(&outvine);}invine->nuke(&invine);return(outvine);}vine    *getpath(hexinfo *from, hexinfo *to, unitinfo *inunit){//// Return a vine of hexes to get unit from from to to.//  or null if there is no valid path.//unsigned int    unsetflag;vine            *vpath=0;vine            *v;vine            *closebuffer;astarinfo       *currentasi;astarinfo       *asiptr;hexinfo         *hptr;hexinfo         *neighbor;pathdef         *pdptr;path            *pptr;int             tt;                     // travel time;pfhash          *pfhashbar=new pfhash();pfhashbar->init(from,to);while(currentasi=pfhashbar->getbest()){        unsetflag=0;        closebuffer=0;        (new vine(ASI,currentasi))->top(&vpath);        hptr=currentasi->hex;        if (hptr==to){                // if we're there, return the path.                 v=asitohex(vpath);		 delete pfhashbar;		 return(v);        }        // otherwise, open neighbors, and set their steps.        for (v=hptr->paths;v;v=v->next){                pptr=(path *)v->data;                if (hptr==pptr->from){                        neighbor=pptr->to;                }else{                        neighbor=pptr->from;                }                asiptr=pfhashbar->ptrtoasi(neighbor);                if (asiptr->ocu){                        // if the hex is unset                        pdptr=pptr->ptype;                        tt=pdptr->traveltime(inunit,pptr);                        if (tt==-1){                                // then that path is unpassable.                                //  add it to the close buffer, if no valid paths go to it, then it will be closed.                                (new vine(ASI,asiptr))->insert(&closebuffer);                        }else{                                // otherwise, add the steps to get here to the asi, and open it.                                asiptr->ocu=1;                                if (asiptr->steps==0||(asiptr->steps>currentasi->steps+tt)){                                        // if the steps in asiptr is 0, it's new; reset steps.                                        // if the steps in asiptr is more, we just found a quicker path.                                        //  which is possible/likely to occur when the unit can fly and walk.                                        unsetflag=1;                                        asiptr->steps=currentasi->steps+tt;                                }                        }                }        }        if (closebuffer){                for (v=closebuffer;v;v=v->next){                        if (asiptr->ocu==2){                                // if the hex is still unset, then there's no valid path to it                                //  close it.                                asiptr->ocu=0;                        }                }                closebuffer->nuke(&closebuffer);        }        currentasi->ocu=0;        if (!unsetflag){                // then the current hex couldn't continue on the path.                //  close it, and pop the vine.                // currentasi->ocu=0;                vpath->remove(&vpath);        }}// if we get here, then there's no valid path.delete pfhashbar;return(0);}

Kindly copy/paste the above into whatever IDE you prefer, to make it more readable.

[Well, "more" readable; I'm still working on that nicely formatted code thing :P ]

So; step by step:

First, I define a few things that can be tweaked. HASHSIZE is the size of the hex lookup table I use later. The WEIGHTs are tweakable settings for the algorithm. For instance it might be more valuable to the pathfinder to move an increment of Z [since there's only a few Z paths] than the others... AP PER HEX is a ratio of coordinate distance to how many AP [action points] a unit is likely to take to move that distance. Basically, moving 1 coordinate is "guessed" to take 2 AP. This, like the rest, is defined so I can tweak things easily to see what works the best.

Next is the struct definition astarinfo. It has a pointer to the hex it represents, and a few ints to maintain the algorithm counters. For those also looking at another A* tutorial, steps is the G [or movement cost to get to that node] and left is the H [heuristic guess of how much is left to travel]. ocu is a state toggle to indicate wether that node is open, closed, or unset as per the algorithm's definition.

Next is a hash table definition. Once again, this is just a generic hash table [or std::map I believe]. Since I expect to do many astarinfo lookups, I chose to use the hash table to speed that process up. Once again, your milage may vary...

pfhash::add serves a dual purpose. It encapsulates the hexinfo pointer within a astarinfo object, and it puts the astarinfo object into the table so I can retrieve it more quickly when I need it again. By default, all nodes are unset; as per the algorithm.

pfhash::init creates astarinfo objects for each node of the map. An important thing to note is that it also calculates the "guess" required by A*. For my implimentation, I simply guess the distance between that hex and the target hex, and multiply by the tweaks defined earlier. It also sets the start node to open, so that the main pathfinding function will start there.

pfhash::ptrtoasi simply does a table lookup returning the astarinfo object which contains the hexinfo being worked on.

pfhash::getbest is a function to find the current "best guess" for A*. For those looking at other tutorials, the F value. For practical purposes, this is the area that could use the most improvement I think.

Now to getpath...

This is the main function. It will be used by the rest of the game for pathfinding. It takes a pointer for the start node, a pointer for the end node, and a pointer for the unit that will be doing the moving. Passing the unit allow allows me to make judgements based on how the unit travels. It will also allow me in the future to not return a path which leads the unit into enemy territory, or too far from home, or anything else really... It returns a vine of hexes. I perhaps will change this to a vine of paths. Either way, the path is defined for whatever requested it.

First thing, I init variables, and the hash table. Remember that pfhash::init also calculates all of the "guesswork" required by A*.

Next comes the main loop. Since only the start node is open, that is what is picked during the first iteration. Should there not be any "open" nodes left, pfhash::getbest returns NULL, ending the loop, and making the function return NULL [cannot get there from here]. Otherwise it picks the "best" open node, as defined by A*.

unsetflag is a flag to determine if this loop iteration opens any nodes. If it doesn't; we've hit a dead end, and need to retrace our steps.

closebuffer is a vine I added to allow for nodes that cannot be reached to be closed, but only after they've all been tried. In A*, any node that is unreachable because of a wall or something is supposed to be closed. In my design, two hexes may [and commonly do] have multiple paths between them. Just because one path is unpassable, doesn't mean another couldn't be used. Hexes that are considered "unpassable" once are added to the vine, so I can double check at the end of the loop that they weren't opened later by another path. If they weren't, then I close them, as the algorithm requires.

vpath is a vine which keeps track of the path so far. The mangled line of code 3 into the loop simply adds the best guess to the top of vpath. If later I come to a dead end, then the best guess will be popped off vpath, and the loop will try the 2nd best guess...

Next I check if the current "best" is the actual target. If so, I convert the astarinfo vine into a hexvine and return it. [and don't forget to clean up before returning...]
The next part loops through the paths from the current node, and opens all of the unset nodes adjacent to it. It sets the newly opened nodes' "steps" [or movement points needed to get to that node]. When the main while() loop restarts, it will use this to pick the best "next step" in the path until it gets to where it's going, or until it can't go anymore.

And that is your arbitrary dimension A* implimentation. I'll apologize now for the poor 'tutorial' and the ugly code, but it works, and I'll certainly try to answer any questions anyone has...

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS