Jump to content

  • Log In with Google      Sign In   
  • Create Account


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.

  • You cannot reply to this topic
17 replies to this topic

#1 Zipster   Crossbones+   -  Reputation: 580

Like
Likes
Like

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!

Sponsor:

#2 ZoomBoy   Members   -  Reputation: 162

Like
Likes
Like

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

#3 UraniumRod   Members   -  Reputation: 122

Like
Likes
Like

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 ''*'' )

#4 Khawk   Senior Staff   -  Reputation: 1360

Like
Likes
Like

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


#5 Kylotan   Moderators   -  Reputation: 3333

Like
Likes
Like

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

#6 ZoomBoy   Members   -  Reputation: 162

Like
Likes
Like

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

#7 Zipster   Crossbones+   -  Reputation: 580

Like
Likes
Like

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.

#8 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

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.


#9 Armitage   Members   -  Reputation: 122

Like
Likes
Like

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.

#10 Kylotan   Moderators   -  Reputation: 3333

Like
Likes
Like

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?

#11 Zipster   Crossbones+   -  Reputation: 580

Like
Likes
Like

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

#12 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

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

#13 ZoomBoy   Members   -  Reputation: 162

Like
Likes
Like

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


#14 ZoomBoy   Members   -  Reputation: 162

Like
Likes
Like

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


#15 DrJohnB   Members   -  Reputation: 122

Like
Likes
Like

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

#16 ZoomBoy   Members   -  Reputation: 162

Like
Likes
Like

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


#17 Zipster   Crossbones+   -  Reputation: 580

Like
Likes
Like

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

#18 edA-qa   Members   -  Reputation: 122

Like
Likes
Like

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.



PARTNERS