View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# A*, plz help!

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.

17 replies to this topic

### #1Zipster  Members

Posted 04 April 2000 - 09:24 AM

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!

### #2ZoomBoy  Members

Posted 04 April 2000 - 04:04 PM

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

### #3UraniumRod  Members

Posted 04 April 2000 - 04:10 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 ''*'' )

### #4Khawk  Senior Staff

Posted 04 April 2000 - 04:49 PM

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

### #5Kylotan  Moderators

Posted 04 April 2000 - 11:01 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

### #6ZoomBoy  Members

Posted 05 April 2000 - 04:07 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

### #7Zipster  Members

Posted 06 April 2000 - 10:07 AM

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.

### #8Anonymous Poster_Anonymous Poster_*  Guests

Posted 06 April 2000 - 09:57 PM

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.

### #9Armitage  Members

Posted 07 April 2000 - 12:17 AM

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.

### #10Kylotan  Moderators

Posted 07 April 2000 - 02:44 AM

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?

### #11Zipster  Members

Posted 07 April 2000 - 09:54 AM

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!!

### #12Anonymous Poster_Anonymous Poster_*  Guests

Posted 07 April 2000 - 10:18 AM

Zipster--you remind me of a young kid who is not such a little kid anymore--myself! I, captain freedom, when I was eight, went to classes at MIT to learn more on A*, Djkistra, and other such path-finding algorithms to find my path through life (easily). However, they all pointed to one thing--Super hero! Thus, I became the super hero as you see me today!

As you might know, I am the bird, the plane, the super hero that watches over all my superbuddies to make sure they get their share of Snickers, and the Freedom DancE! So, my point is that the Freedom BLASTER needs fixing--so, if you could fix it, come over to the High COMMANDER Plaza in Supercity, Freedomland, USA ASAP!!

My hobbies include eating snickers, doing the freedom dance, drinking coffee, and using super powers.

May freedom help you cope with life...
Captain FREEDOM!!
Destroyer of evil, bringer of good news...
(More good news to come)...

### #13ZoomBoy  Members

Posted 07 April 2000 - 02:45 PM

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

### #14ZoomBoy  Members

Posted 08 April 2000 - 02:00 AM

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

### #15DrJohnB  Members

Posted 08 April 2000 - 03:02 AM

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

jmbianchi@yahoo.com

### #16ZoomBoy  Members

Posted 08 April 2000 - 03:24 AM

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

### #17Zipster  Members

Posted 11 April 2000 - 10:20 AM

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.)

### #18edA-qa  Members

Posted 11 April 2000 - 12:25 PM

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.

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.