Take the 2-minute tour ×

I'm working on an adventure game in Python using Pygame. My main problem is how I am going to define the boundaries of the room and make the main character walk aroud without hitting a boundary every time. Sadly, I have never studied algorithms so I have no clue on how to calculate a path. I know this question is quite general and hard to answer but a point in the right direction would be very appreciated. Thanks!

share|improve this question
Are you controlling your main character yourself ? or is it some kind of AI moving around by itself ? –  Andrew Keith Oct 26 '09 at 6:25
add comment

4 Answers

up vote 3 down vote accepted

I recommend you read up on the A* search algorithm as it is commonly used in games for pathing problems.

If this game is two dimensional (or 2.5) I suggest you use a tile system as checking for collisions will be easier. Theres lots of information online that can get you started with these.

share|improve this answer
Thanks alot. I am currently looking into this pygame.org/project-AStar-195-.html –  kallepersson Oct 27 '09 at 10:28
add comment

There are two easy ways of defining your boundaries which are appropriate for such a game.

The simpler method is to divide your area into a grid, and use a 2D array to keep track of which squares in the grid are passable. Usually, this array stores your map information too, so in each position, there is a number that indicates whether that square contains grass or wall or road or mountain etc. (and therefore what picture to display). To give you a rough picture:

#.#  #
# ## #
#    #

A more complex method which is necessary if you want a sort of "maze" look, with thin walls, is to use a 2D array that indicates whether there is a vertical wall in between grid squares, and also whether there is a horizontal wall between grid squares. A rough picture (it looks a stretched in ASCII but hopefully you'll get the point):

 - - - -
| |     |
   - - 
|       |
 - - - -

The next thing to decide is what directions your character may move in (up/down/left/right is easiest, but diagonals are not too much harder). Then the program basically has to "mentally" explore the area, starting from your current position, hoping to come across the destination.

A simple search that is easy to implement for up/down/left/right and will find you the shortest path, if there is one, is called Breadth-First search. Here is some pseudocode:

queue = new Queue #just a simple first-in-first-out
while not queue.empty():
    exploreNode = queue.pop()
    if isWalkable(exploreNode): #this doesn't work if you use
                                #"thin walls". The check must go
                                #where the pushes are instead

        if isTarget(exploreNode):
            #push all neighbours
            queue.push( exploreNode.up )
            queue.push( exploreNode.down )
            queue.push( exploreNode.left )
            queue.push( exploreNode.right )

This algorithm is slow for large maps, but it will get you used to some graph-search and pathfinding concepts. Once you've verified that it works properly, you can try replacing it with A* or something similar, which should give the same results in less time!

A* and many other searching algorithms use a priority queue instead of a FIFO queue. This lets them consider "more likely" paths first, but get around to the roundabout paths if it turns out that the more direct paths are blocked.

share|improve this answer
Thanks a LOT for this thorough description. It helped me understand algorithms better! I am probably settling for the A* algorithm since it does most of the thinking for me :) Size of the map might be a problem with A* though, since the current implementation I'm using (pygame.org/project-AStar-195-.html) works quite slowly with a 1024x768 map. Perhaps I should make every map tile bigger and decrease the total amount of tiles. –  kallepersson Oct 27 '09 at 10:43
Why is your map so large? 1-pixel tiles are far too small. If you want your game world to be "hand drawn" rather than painted from tiles, a reasonable solution is to also draw an (invisible) map of passable/impassable areas, with say 4x4 pixels to each square in this map. You can also make A* "smarter" in various ways, for instance by making a distinction between "local" travel and "global" travel. Or you could just limit how far A* is willing to look, and otherwise force the user to click somewhere easier to get to. –  Artelius Oct 27 '09 at 12:39
Yes, 1-pixel tiles are definedly too small. To clarify, I am making my map suitable for a world with a 2.5D perspective (like Monkey Island 3 for instance). Even so, you are right in that I don't need 1px tiles. 4 or even 10pixel tiles would be well than enough. The tiles will be invisible. Thanks for your advice. –  kallepersson Oct 27 '09 at 13:58
I also plan to import the map from a svg for easy modification of each room. –  kallepersson Oct 27 '09 at 14:11
add comment


Before you start writing games, you should educate yourself on those. This takes a little more effort at the beginning, but will save you much time later.

share|improve this answer
Thanks! I am currently looking into the A* algorithm. –  kallepersson Oct 27 '09 at 10:27
add comment

I am not familiar with pygame, but many applications commonly use bounding volumes to define the edge of some region. The idea is that as your character walks, you will check if the characters volume intersects with the volume of a wall. You can then either adjust the velocity or stop your character from moving. Use differing shapes to get a smooth wall so that your character doesn't get stuck on the pointy edges.

These concepts can be used for any application which requires quick edge and bounds detection.

share|improve this answer
add comment

Your Answer


