Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  A* Pathfinder tutorial  (Read 3465 times)
0 Members and 1 Guest are viewing this topic.
Offline Woz

Senior Newbie




A Troll who lives in a hole


« Posted 2003-05-02 10:26:43 »

Hi  all,

I've recently had the pleasure of debugging a friends A* pathfinder routine, and decided to write a tutorial on the subject.

For those that don't know A* is able to find the shortest path between two points avoiding objects in the way.

Which can be located : http://RealmDesigns.Russki.net/?command=tutor&t=3

It is broken down into easy to follow steps, so its relatively painless to follow.

It also covers some of the common pitfalls that will be encountered and performance problems like how to deal with heuristic failure (which is why I've posted it in this forum - moderator shoot me if I'm wrong!)

There is no code, so Cut & Paste Queens will be disappointed..

Anyone implementing it in a real-time enironment is going to have to work on their optimization in order to get lots of objects moving!

I'd certainly like to hear from peoples experience!!
Data structure is definately the key, in order to eliminate the sort per move.

All the best.
------
Woz.

P.S.
Tutorial 2 (Garbage Collection, and how to avoid it) keeps getting bigger and bigger so it isn't finished (probably wont for some time).
But it should at least be interesting!
Offline mill

Junior Devvie




popcorn freak


« Reply #1 - Posted 2003-05-02 11:11:39 »

i think this belongs to the AI section (http://www.java-gaming.org/cgi-bin/JGOForums/YaBB.cgi?board=AI)

Offline bmyers

Junior Devvie





« Reply #2 - Posted 2003-05-02 13:09:37 »

Yes, it should go in the AI section.

And it's a nice tutorial!

For some other A* tips, I've found the AI Game Programming Wisdom book which was just released to be very good as well.  Although a lot of the A* stuff deals with C++ optimizations that are not applicable to Java.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Luke

Senior Newbie




I love YaBB 1G - SP1!


« Reply #3 - Posted 2003-05-03 09:41:47 »

My A* tip would be start by adding the target(s) to the open list rather than the starting position.  This lets you solve problems like 'Find the path to the nearest exit.' where there are several exits more easily.

My question is does any one have any links/code/ideas on the best way to write an efficient priority queue for the open list.

Luke
Offline mill

Junior Devvie




popcorn freak


« Reply #4 - Posted 2003-05-03 10:12:28 »

forgot to mention that the tutorial was very nice indeed.

Offline Woz

Senior Newbie




A Troll who lives in a hole


« Reply #5 - Posted 2003-05-03 14:35:02 »

A typical link list will allow you to insert nodes anywhere in the list.

If you order your link list correctly (not difficult) the nearest node (to the target) will always be at the top, first in the list.

This looks clean in an implementation, but the memory distribution of (the link list) Objects is not contiguous, in that they could located be anywhere in ram. This will generate cache misses (a bad thing).

Although modern Generation Garbage Collection suggests that objects are grouped by age, unfortunately the cache is so small that it will not cover each generations collection of objects (several meg each, or even bigger), the objects are not guaranteed to be localised enough to be in the cache all at the same time.

This is always a major draw back of Object Orientated Languages, which is FAR MORE serious for Java because it does not support structures, which could be used to greater effect in this situation. Although you are not going to get linear memory access (it's a link list after all) at least each link will be very close to the next.

It does, however, eliminate the need for sort the open list each iteration as you can just insert your nodes (typically only 3, 5 if moving diagonally).

I would strongly suggest using a pool of object, to remove any GC activity that WILL occur.

It soon turns into quite a heavy piece of code, simply because it has to be fast (unless your not using it in a real-time situation).

Of course you could always just call it every other frame (or even less). For those that like using Threads it could be possible to stick everything in a round-robin style list and stick it on a low priority and have it running in the back ground, refeshing targets when possible.

------
Woz.



Offline Luke

Senior Newbie




I love YaBB 1G - SP1!


« Reply #6 - Posted 2003-05-05 21:18:54 »

Thanks for the reply.

If I use a linked list, is there a smart way to find the right place to insert an entry, or is it best just to start at the bottom and work up until the correct place is found?  Another complication seems to be that before an entry is added, you need to check whether it is already on the open list, and this will involve checking every entry in the list unless a more sophisticated data structure is used.  Is there a standard way of solving this problem?  (Btw, I haven't done a CS degree, so apologies if I'm missing something that seems obvious).

Luke
Offline Woz

Senior Newbie




A Troll who lives in a hole


« Reply #7 - Posted 2003-05-06 09:00:39 »

Luke,

A linear search will suffice, as the list is ordered always start at the end nearest to the target location (I assume bottom in your case, but I have a tendency to visualise it at the top - just like the stack in the example).

Because A* always tries to move closer to the target each iteration, it makes sense that each node will either be equal to or grater than the value on the top of the stack (if not very close to it). So you will usually only have to search the first few nodes.

(When I say value I mean the distance value from the current location to the target location).

Unless your map has lots of obstacles, and so may make several wrong decisions, a link list will be fine.

On a map with lots of obstacles you will need to start using a different data structure, like a binary tree, so that you can find the location to insert at quicker (as it could be anywhere in the list). A binary tree will accelerate the search into a binary search, which divides the data set in halve repeatedly until it has found the appropriate location.

In order to simplify and accelerate the check to see if the node is already on the open list, you can use a 2 dimensional array for each location on the map, true for already on the open list, false for available to use.

Most people will reduce this down to a single large array, or use a bitmap to save some space.

------
Woz.

P.S.
Don't worry about the CS degree, you don't need one to be able to write good code.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (36 views)
2014-12-15 09:26:44

Mr.CodeIt (29 views)
2014-12-14 19:50:38

BurntPizza (61 views)
2014-12-09 22:41:13

BurntPizza (98 views)
2014-12-08 04:46:31

JscottyBieshaar (58 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (76 views)
2014-11-29 21:32:03

toopeicgaming1999 (137 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36

toopeicgaming1999 (37 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!