Adventure game - walking around inside a room

Question

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!

Answer 1

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.

Answer 2

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
queue.push(startNode)
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):
            #success!!!
        else:
            #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.

Answer 3

Sadly, I have never studied algorithms so I have no clue on how to calculate a path.

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.

Answer 4

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.