A*, plz help!

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

This is probably a little off topic but why is the ''I'' in ''AI'' asterisked? (if you don''t know what that means or I spelt it really bad its a ''*'' )

quote:

---

Original post by UraniumRod

This is probably a little off topic but why is the ''I'' in ''AI'' asterisked? (if you don''t know what that means or I spelt it really bad its a ''*'' )

---

Actually, A* refers to the A* pathfinding algorithm. :-) It''s just one of the topics under AI.

Kevin

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.

Yeah. His pseudo-code and his try-out program, well, they really made it a piece of cake to understand it all, I think. I have yet to find another article that explains it that clearly.

A polar bear is a rectangular bear after a coordinate transform.

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?

I already downloaded that cool AI demo thingy, and I saw it in action, so I know the basic idea, but now i guess implementation is the problem. Watch this:

IMPLEMENTATION!

That was tight yo!!

quote:

---

Original post by Zipster

I already downloaded that cool AI demo thingy, and I saw it in action, so I know the basic idea, but now i guess implementation is the problem. Watch this:

IMPLEMENTATION!

---

IMPLEMENTATION boils down to a list of questions completely answered one

after

another.

1) What sort of space do you have: Tiles, Hexes, Flat-Space 3-D ??

it is THE question because, while the priciples of A* remain the same, the implementation changes drastically with the space type. You usually end up adapting either the space or the search by their interactions. Implementation also uses your collisions detection methods.

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

In a step-by-step process, maybe you should build a quick-path generator 1st. It would just give you a list of tiles or hexes or points but didn''t worry about any obstacles. This would set up: path-storage for the object moving and help you choose how to implement A*

So I built a path creator 1st for my hex-surface. From, tada, the Starting Point, it looks at the nearest 6 hexes and, using a squares-of-the-distance( [(TargetX - CurrentX)^2 + (TargetY - CurrentY)^2] chooses the lowest cost hex). I store that direction(0 to 5) on my list( actually a string of 70 chars like "00011222332212xxxxxxxx")
I then chose too examine that "best" hex(the six hexes around it and keep repeating until the CurrentX+Y are the target.

With a flatspace it''s like you have to draw a line to a point and check to see if it intersects any thing. So you''ve got to build a line intersection function.

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

Can someone please send me a link to his "PathDemo" program? I can''t seem to find it. Thanks.

jmbianchi@yahoo.com

Find a link for his path-demo at Amit P''s AI web-site, under shortest path It''s my favorite for all types of missions.

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

Heh, I guess I can just ask my senior programmer friend at Westwood Studios for some AI tips...

*DISCLAIMER*:
The above information is 100% true. Zipster (whoever he may be)DOES know a senior programmer at Westwood Studios.)

A* is somewhat related to the Djikstra algorithm -- the difference being that A* uses a heursitic (i.e. an estimate of the cost) to help speed along the algorithm.

Djikstra''s is easier to explain (firstly). Basically it blindly searches from a start point: it checks every path recursively until it finds a path that happens to have the end point (or destination) in the path. As it iterates through the paths, should it ever find a path to a place it''s already been, and this new path is shorted than the existing one, it replaces the old path. Therefore Djikstra''s will eventually find the shortest path to every place on a map (of course you''ll stop when you reach the desired destination).

Note that Djikstra always searches the shortest path first, which leads to a kind of breadth-first search.

A* is a modification that effects the breadth-first approach. Basically each location is also assigned an estimate of how far from the destination it is (on a simple grid this can be as simple as the length of the line from the location to the end point). A* then basically rules out estimated costly paths in favour of less costly shorter paths.

This produces the same result (albeit) quicker, if the estimate is never greater than the actual cost from that location. If you start increasing the estimate above the actual cost, your algorithm will likely start to find paths quicker and quicker, but they are no longer guaranteed to be the "best" path.

Chosing the estimate is the most difficult part of the A* algorithm.