In many games you want opponents, npc's, enemies etc... to
interact with the player and show certain intelligence when moving
around ie: you want them to avoid obstacles, plan routes and
generally not bump into everything in their path when moving
around! To aid in this GameMaker: Studio has a series of
functions that deal with motion planning.
Motion planning in GameMaker: Studio is dealt with by the
mp_ functions, which themselves are split into three
groups:
This kind of function tries to compute a collision-free path for the instance. Once this path has been computed you can assign it to the instance to move towards the goal. The computation of the path will take some time but after that the execution of the path will be fast. Of course this is only valid if the situation has not changed in the meantime. For example, if obstacles change you possibly will need to recompute the path. Again notice that these functions might fail and that no path is found for the instance.
These are the basic avoidance functions and good for simple AI. They work by making an instance take a step towards a particular goal position while trying to go straight if possible but taking a different direction if required. These functions should be used in the step event of an instance.
The final type of function use a much more complex mechanism
based on a grid-based approach (sometimes called an A* algorithm).
It will be much more successful in finding paths (although it still
might fail) and will find the shortest paths possible but it
requires more work on your side to set it up.
The global idea is as follows - First of all we create a grid that
covers the room (or the relevant part of it). You can choose to use
a fine grid, which will be slower, or a coarse grid, but both of
them should be based on the resolution of the room so that the
path-finding is as accurate as possible. For example, if you have a
room that is 400x200 pixels, you can have a grid resolution of 40,
or 20, or 10... it all depends on how accurate you need the path to
be and how much processing you want GameMaker to do to generate
it.
Next, for all relevant objects that we want to avoid we need to
determine the grid cells they overlap (based either on their
bounding boxes or their precise sprite) and mark these cells as
being forbidden. So a cell will be marked totally forbidden, even
if an obstacle is only partially overlapping.
Finally we specify a start position and a goal position, both of
which must lie in free cells, and the function then computes
the shortest path possible between these two positions. The path
will run between the centers of all free cells, so if the cells are
large enough so that the instance placed at its center will lie
completely inside it this will be successful. This path is then
assigned to the instance to follow using the path_ functions. You should
realise how important cell size is for this as the cells must be
large enough so that the moving object placed with its origin on
the center of a cell will lie completely inside the cell.
(Be careful about the position of the origin of the object. Also
realize that you can shift the path if the origin of the object is
not in its center!) On the other hand, the smaller the cells the
more possible paths exist. If you make cells too large, openings
between obstacles may get closed because all cells intersect an
obstacle.
The grid-based approach is very powerful (and is used in many
professional games) but it requires that you do some careful
thinking as you must determine which area and cell size are good
enough for solving the game. Also, you must determine which objects
must be avoided and whether precise checking is important. All
these parameters strongly influence the efficiency of the approach.
You must also decide whether it is actually necessary as maybe one
of the less costly mp_ functions can do the job just as well.
Whatever you choose, it should be noted that in many situations not
one of the above will give you a perfect solution and that you will
have to "mix and match" the functions, using one or the other
depending on the situation within your game.