Meilleur Pathfinding

The other functions use a much more complex mechanism using a grid-based approach (sometimes called an A* algorithm). It will be more successful in finding paths (although it still might fail) and will find shorter paths but it required more work on your side. The global idea is as follows. First of all we put a grid on (the relevant part of) the room. You can choose to use a fine grid (which will be slower) or a coarse grid. Next, for all relevant objects we determine the grid cells they overlap (either using bounding boxes or precise checking) and mark these cells as being forbidden. So a cell will be marked totally forbidden, even if it only partially overlaps with an obstacle. Finally we specify a start and a goal position (which must lie in free cells) and the function computes the shortest path (actually close to the shortest) between these. The path will run between centers of 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 you can now give to an instance to follow.

The grid-based approach is very powerful (and is used in many professional games) but it requires that you do some careful thinking. 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.

In particular the size of the cells is crucial. Remember that the cells must be large enough so that the moving object placed with its origin on the center of a cell must 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 actual functions for the grid-based approach are as follows:


mp_grid_create(left,top,hcells,vcells,cellwidth,cellheight) This function creates the grid. It returns an index that must be used in all other calls. You can create and maintain multiple grid structures at the same moment. left and top indicate the position of the top-left corner of the grid. hcells and vcells indicate the number of horizontal and vertical cells. Finally cellwidth and cellheight indicate the size of the cells.
mp_grid_destroy(id) Destroys the indicated grid structure and frees its memory. Don't forget to call this if you don't need the structure anymore.
mp_grid_clear_all(id) Mark all cells in the grid to be free.
mp_grid_clear_cell(id,h,v) Clears the indicated cell. Cell 0,0 is the top left cell.
mp_grid_clear_rectangle(id,left,top,right,bottom) Clears all cells that intersect the indicated rectangle (in room coordinates).
mp_grid_add_cell(id,h,v) Marks the indicated cell as being forbidden. Cell 0,0 is the top left cell.
mp_grid_add_rectangle(id,left,top,right,bottom) Marks all cells that intersect the indicated rectangle as being forbidden.
mp_grid_add_instances(id,obj,prec) Marks all cells that intersect an instance of the indicated object as being forbidden. You can also use an individual instance by making obj the id of the instance. Also you can use the keyword all to indicate all instances of all objects. prec indicates whether precise collision checking must be used (will only work if precise checking is enabled for the sprite used by the instance).
mp_grid_path(id,path,xstart,ystart,xgoal,ygoal,allowdiag) Computes a path through the grid. path must indicate an existing path that will be replaced by the computer path. xstart and ystart indicate the start of the path and xgoal and ygoal the goal. allowdiag indicates whether diagonal moves are allowed instead of just horizontal or vertical. The function returns whether it succeeded in finding a path. (Note that the path is independent of the current instance; It is a path through the g rid, not a path for a specific instance.)
mp_grid_draw(id) This function draws the grid with green cells being free and red cells being forbidden. This function is slow and only provided as a debug tool.