I need a really good site that explains it the idiot way. I went to Amit''s site and that was too complicated to understand. Plz help!! I know what it is and all, but what i need is an explanation on how it works!

There's a good basic tutorial at
Justin Heyes-Jones A* Tutorial

A* varies very much depending on the playing surface that you use. I have hex-tile surface and each node(hexagon) has data stored like
struct mapinfo
{
char obstacle;
short int hexsidescost[6];
struct mapinfo *parent, *lnext, *lprev; // linked-list info
// *parent has a different function than *lnext, *lprev
unsigned char height;
short xhex, yhex;
int g;
int h;
int f;
unsigned char listflag;
...
...
} *CEMap[MAXCOL][MAXROW];

There's a lot of pseudo-code out there rather than real code because you have several choices to make
Where are you going to store the pathlist info? Inside each node like I did or on a separate linked-list OR queue OR stack?
How do you store the path generated? If you take a look at my diary you'll see I had problems with this even though I had generated a good path.
If you do not have discrete nodes, like I have, how do you create them. Bryan Stout had a very good but short discussion on that Also check out his full article starting at _Introduction_

The final result of A* searching is a linked list from the destination node to the starting node through the *parent pointer.
Starting from the destination node, I compared it to the its parent node and got a direction(0 through 5(6 direc tions for a hex)) from that. That direction I inversed it (parent===>destination) and I stored on a list/array. I looked at the parent node and compared it to _its_ parent and got a direction and so on until I arrived at the starting position.

You are going to have to sit down with a map of your area and make those decisions. It'll take some plotting on paper but follow the pseudo-code closely.
If you do not understand linked-lists and have no experience in them, don't bother trying this AI stuff. Before I did my path-finding, I learned, from other projects, how to create and manipulate linked-lists. Though sometimes I get lost in the insertion(what goes before what) I just copied over my linked-list code and modified it slightly. If you take a look at my DOS RPG editor, it's nothing but linked-lists. Pointers are your friends. Or if you need queues or stacks, program in them 1st and learn how to insert properly. C++'s STL(Standard Template Library) has some good stuff for that.


ZoomBoy
A 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor and diary at
Check out my web-site


Edited by - ZoomBoy on 4/4/00 10:07:21 PM

quote: Original post by ZoomBoy

If you do not understand linked-lists and have no experience in them, don't bother trying this AI stuff.

Any programmer, game or otherwise, would do well to learn the basics of linked lists, stacks, queues, heaps, maps, hash tables etc. Arrays are rarely a satisfactory solution for situations where you don't know beforehand how many of something you are going to need (and especially where it could be a large number), for instance units, projectiles, nodes in a pathfinding algorithm, etc. Pick up a cheap algorithm book, or find a site online that describes these things.

quote: Or if you need queues or stacks, program in them 1st and learn how to insert properly. C++'s STL(Standard Template Library) has some good stuff for that.

STL has some quick implementations of the above container types. And once you've learnt how to use one type, you know the basics of using all of them. I recommend learning how to write your own lists, queues, etc, but STL is a good and standard way to use these containers quickly.

(PS. This is not directed at ZoomBoy, but at anyone who thinks game programming doesn't involve all these things. You will need to learn them at some point if you want to be any good, and the sooner you do, the sooner you can write good code.)

Edited by - Kylotan on 4/5/00 5:03:18 AM

quote: Original post by Kylotan

STL has some quick implementations of the above container types. And once you've learnt how to use one type, you know the basics of using all of them. I recommend learning how to write your own lists, queues, etc, but STL is a good and standard way to use these containers quickly.

After you've learned linked-lists, you appreciate not having to debug them. STL just lessens the errors for a procedure you should already know clearly.

ZoomBoy
A 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor and diary at
Check out my web-site


Edited by - ZoomBoy on 4/5/00 8:16:52 PM

OK, then, back to the original problem guys

I understand pointers linked lists, the works. I''ve been working in C++ for years. But when I started to work on path-finding, A* confused me. I think it was that the article I read on it wasn''t that good (not the one above), and I need the idiot''s explanation on what A* does, why it works, etc.

I''ve also heard of Tracing, Robust Tracing, Dystki (or whatever), and others, but A* it says is the best all around one.

The only way to understand it, is to visualize it, so get Bryan Stout''s
path-finding program off of Gamasutra and run it. You can watch as
the algorithm searches out its surrounding nodes and tries to find its
target.

quote:Original post by Zipster

I need the idiot''s explanation on what A* does, why it works, etc.

Well, one ''brute force'' method is Breadth First Search, where you start from the origin, check all adjacent squares, if you''re not yet at the goal, check all the squares adjacent to that, and so on. Imagine a circle centred on the origin that gradually expands until it reaches the goal. Everything within that circle was checked to see if we had reached the goal.

A* takes the basic Breadth First Search, and uses some information you provide it about your map (the heuristic) that allows it to make an intelligent choice, so that instead of naively searching in all directions equally, it can search in what it believes to be the best direction first. In fact, it ends up looking more like a Depth First Search when it works well, since it heads straight for the target.

Does that help any?