My favorites | Sign in
Project Home Downloads Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
AStar_Implementation_Guide  
AStar Guide
Updated May 18, 2007 by cau...@gmail.com

Sources

Yea i didnt make it myself. ^^ Reference the Astar class to: AStar - 1.1 John Eriksson (wmjoers)

This Astar example will help us alot, in creation of the map.

Technical

Map

I think this is how we should create the map as:

Cells will be created (as we have already mentioned.

However how do we know which cells are filled or not?

This can be worked out via simple calculations:

Resolution / 16

Our resolution of the game is 800x480

Therefore the grids within the program will be 50x40. Therefore 200 Grids

The Map System should accept 2 values a X and Y. Which are screen resolution values, for example:

x=405, y=226

convert to grid co-ords:

x=25.31, y=14.12

truncate them and there ya got it... your block

We can have a invisible layer on top, where the method prints a block ontop.

Those co-ordinates can be easily obtained via the MapCreator Python program in SVN.

A Star Algorithm

Basically the A Star Algorithm needs to know 3 things, Start and End Point, and obstacles. Obstacles can be read from file, as described above on how to create the Map.

Dan, I have left the end points in the Python program to allow you to mess around. Everybody on the map, including Humans and AIs will have a AStar Class which will guide them from 1 point to the 2nd point.

For humans: When you click on the position it will say "Me.StartingPoint" go to "Click.EndingPoint" work out the path and i follow this.

For AIs: it will be similar however it will just choose for example the closest target.

Collision Detection

There is no need for Wall collision detection using this system, since all the walls are defined. A star will always choose the closest path there, also it will avoid walls too, since it knows where they are, and will create a path that will avoid the wall.

Try it out, build a wall and put each end node beside it... it will go around the wall.

Code

Astar.py - AStar Implementation, this is the container for all the methods and classes related to the AStar Algorithm, modifications shouldnt need to be done....

MapMaker.py - Map Making Program, you may use this to create your map, and use this as reference to implementing the AStar. Basically just chop up the code and stick it into ours.... copy and paste and modify it to what we need.

MapMaker.py

Methods

initMap - sets up the map with the correct values, and makes the drawable layer on top... so you can place black squares. Sets the start and end points (this will have to be set at start of battle)

drawMap - Use this to draw the map on screen... the map as in the background image. (Empty battle field with walls on side)

UpdateMap - This is used to update the map... also can be used to set the map. This will have to be called every time you make a modification to the map.

Accepts 3 values: x, y, v

X = the x co-ordinates, this is the grid co-ordinate which is Resolution/16

Y = the y co-ordinates, this is the grid co-ordinate which is Resolution/16

v is the switch:

when V=5 it means this will set the Starting point

when V=6 it means this will set the End Point.

When v is empty or anything else, it will set a Blocking Square (Wall).

DrawMenu - ignore this for implementation into our game. This just draws the menu on that Mapmaking program.

findPath - this will use the AStar algorithm to find the path, there is a few things you can cut out from it, such as time it takes to find the path.... quite worthless in our case.

MainLoop - No real need of explination here simple enough.

Powered by Google Project Hosting