Tutorial:Pathfind demo

From Bennu Wiki
Jump to: navigation, search


Introduction

This is an pathfinding example originally made by TYCO, wich can be found in bennupack in
2 Medium\IA\PATH.FIND\ejemplo_PATH_FIND.prg 

It demonstrates the Path_find() and Path_getxy() functions. The example is quite large, and I translated it by using google translate. I added debugging output with the say() function, so that you can monitor the program as it is running. I recommend to pipe the output to a textfile, this can be done by typing

bgdi pathfind.dcb >output.txt

Once the program has stopped running (by pressing the ESCAPE key), you can then read back everything the program did by opening th file with a text editor.

Please note that the translation is an approximation of the original text, as google translate produces weird stuff, so I changed the texts. If you can read spanish, then I recommend looking at that as well. I made the identifier names as descriptive as possible so that it documents itself.


The working of the program

Some special notes about the program:


- The background bitmap (wich is put in the scroll) has 14 control points, wich are stored in two seperate arrays.

- The coordinate system for the pathfinding and the color checking devides the coordinates by 10.

- The map in the upper right corner is also the bitmap used by the Path_find() function.


The program it self


/*  Based on bennupack example by TYCO: 2 Medium\IA\PATH.FIND\ejemplo_PATH_FIND.prg */

/*  Translated and extra documented by handsource/DYKO */

/* Notes: this program was initially translated to english with google translate, wich gave me */
/* a very rough translation that I had to correct. The longer sections of text where a bit of */
/* a pain to transform, so excuse me for any weirdness. You know, online translaters are not that */
/* clever and translate things literally without taking the context into account. */
/* If you can read spanish (wich I can't) I recommend to read the comments in the original spanish */
/* version. */

IMPORT "mod_say";
IMPORT "mod_debug";
IMPORT "mod_key";
IMPORT "mod_text";
IMPORT "mod_map";
IMPORT "mod_path";
IMPORT "mod_proc";
IMPORT "mod_grproc";
IMPORT "mod_scroll";
IMPORT "mod_video";
IMPORT "mod_wm";
IMPORT "mod_draw";
IMPORT "mod_math";



GLOBAL

    int track;           // graphID of the scenenry (the pretty graphics).
    int world_map;       // graphID of the logic map used by path_find().
    int car;             // graphID of the car sprites.
    int map_checkpoints; // graphID of a map made in memory, 100 x 100 pixels in size.

    int start_car=0;     // Flag that indicates that the race is started or not.
    int counter=0;       // general purpose loop counter.
    
    int text1;           
    int text2;

    // Two arrays that store the x and y coordinates of the controlpoints in the racetrack 
    // (scene) bitmap. The arrays are much larger the nessesary.
    int x_[100];
    int y_[100];
    
    
    // These control points are stored in the two arrays mentioned above. So x values
    // go into the array "_x[]" and y values go in to the array "_y[]".
/*
    These are the controlpoint in the "1PISTA.MAP" file,
    wich is the bitmap for the racetrack.

    control point   x           y
    number
    -----------------------------------------
    0               0           0
    1               875         1126
    2               927         1262
    3               1033        1127
    4               1090        1265
    5               1194        1133
    6               1258        1267
    7               344         1124
    8               350         759
    9               590         638
    10              710         504
    11              895         356
    12              1033        731
    13              1274        932
    14              800         1136
*/
    

    int check_point[6]; // Array wich stores the checkpoints, The first slot
                        // in the array (check_point[0]) is not used.
   
    int enemy_id[6];    // Array wich stores the process id's of the enemies. 
                        // The first slot in the array (enemy_id[0]) is not used.



                        
PROCESS int main(); // The main program.

BEGIN


    set_title("Path Find example by TYCO (translated by handsource/DYKO)");
    set_mode(640,480,8);
    set_fps(20,0);

    track=load_map("1PISTA.MAP");     // The background (racetrack) scene.
    world_map=load_map("2MAPA.MAP");  // The logicmap used by path_find()
    car=load_map("3COCHE.MAP");       // The car sprite.
    
    // Create a scroll, and scroll the racetrack.
    start_scroll(0, 0, track, 0, 0, 0);

    // Show a preview of the "search" map in the top-right corner of the screen, 
    // that is used by the path_find() function.
    show_search_map(565,62,world_map,100,128);
    write(0,505,140,0,"world_map  search");
     
     
    write(0,300,170,0,"Press 1 to 6 to follow target. Press Enter to Start");
    text1=write(0,0,0,0,"");
    text2=write(0,0,0,0,"");


    // Obtain 14 control points from the "race track" scene) bitmap, and store the
    // x and y coordinates in two seperate arrays. The center controlpoint is 
    // controlpoint number 0.
    say("get controlpoints from the '1PISTA.MAP' file.");
    FOR (counter=0; counter<15; counter++)
        get_point(0,track,counter,OFFSET x_[counter],OFFSET y_[counter]);
        say("control point: "+counter+";   X = "+x_[counter]+";   Y = "+y_[counter]);
    END
    
    // After this loop, the array's "_x[]" and "_y[]" will hold these values:
/*
    These are the controlpoint in the "1PISTA.MAP" file,
    wich is the bitmap for the racetrack.

    control point     _x[counter]   _y[counter]
    number 
    (counter value)
    -----------------------------------------
    0                 0             0
    1                 875           1126
    2                 927           1262
    3                 1033          1127
    4                 1090          1265
    5                 1194          1133
    6                 1258          1267
    7                 344           1124
    8                 350           759
    9                 590           638
    10                710           504
    11                895           356
    12                1033          731
    13                1274          932
    14                800           1136
*/   
       
       
    // Create the six car processes, and position them on the controlpoints
    // that are stored in the arrays "_x[]" and "_y[]".
    //
    // enemy (int x, int y, int angle, int unit);
    enemy_id[1]=enemy(x_[1], y_[1], 180000, 1);
    enemy_id[2]=enemy(x_[2], y_[2], 180000, 2);
    enemy_id[3]=enemy(x_[3], y_[3], 180000, 3);
    enemy_id[4]=enemy(x_[4], y_[4], 180000, 4);
    enemy_id[5]=enemy(x_[5], y_[5], 180000, 5);
    enemy_id[6]=enemy(x_[6], y_[6], 180000, 6);

    
    map_checkpoints=new_map(100,100,8); // Create a new bitmap in memory, 100x100 pixels. 
    drawing_map(0,map_checkpoints);     // We are going to draw a circle on it.
    drawing_color(1);                   // A dark red color.
    draw_fcircle(50,50,100);            // Create a solid circle @50,50 with a radius of 100 pix.



    // The main program loop, this controls the start of "race" and the number keys
    // Change the camera to follow the selected car. "ESC" quits the program.
    LOOP
        IF (key(_esc))
           exit("goodbye, end of simulation.",0);
        END
        IF (key(_enter))
           start_car=1;         // Flag that indicates that the race is started.
           say("race started");
        END
        IF (key(_1))
           scroll[0].camera=enemy_id[1];
           say("scroll camera is following car number: 1 [ID="+enemy_id[1]+"]");
        END
        IF (key(_2))
           scroll[0].camera=enemy_id[2];
           say("scroll camera is following car number: 2 [ID="+enemy_id[2]+"]");
        END
        IF (key(_3))
           scroll[0].camera=enemy_id[3];
           say("scroll camera is following car number: 3 [ID="+enemy_id[3]+"]");
        END
        IF (key(_4))
           scroll[0].camera=enemy_id[4];
           say("scroll camera is following car number: 4 [ID="+enemy_id[5]+"]");
        END
        IF (key(_5))
           scroll[0].camera=enemy_id[5];
           say("scroll camera is following car number: 5 [ID="+enemy_id[5]+"]");
        END
        IF (key(_6))
           scroll[0].camera=enemy_id[6];
           say("scroll camera is following car number: 6 [ID="+enemy_id[6]+"]");
        END
        FRAME;
    END
END  // End of main program.





// Enemy "car" process.
PROCESS int enemy(int x, int y, int angle, int unit);

PRIVATE
    int increment_angle=0;
    int final_angle;
    int enemy_velocity=0;
    int maximum_velocity=18;
    int enemy_position=0;
    int previous_checkpoint=-1;
    
    int point_x[256];
    int point_y[256];
    
    int following_point=0;
    int remaining_distance;
    int pixel_color=100;
    
    int path_find_status;  // Hold return value (for debugging purposes).
    int path_getxy_status; // Hold return value (for debugging purposes).
    
    
BEGIN
    ctype=c_scroll;
    z=100;
    size=60;
    flags=3;
    graph=car;


    // Displays the what the next checkpoint of "enemy/car 1" is. 
    // Set the camera so that it put's the car in focus (default).
    IF (unit == 1)
       write(0,10,175,0,"Next CheckPoint:");
       write_int(0,135,175,0,OFFSET check_point[unit]);
       scroll[0].camera=id;
       say("scroll camera is following car ID="+id);
    END

    
    // Main loop
    LOOP
           
        // Values for _x[] and _y[] for a given unit number, remember these two array's
        // store the x and y coordinates of 14 control points. The unit is the "car" number.
        // Wich is also used to index the arrays.
        /*
        unit=0, _x[7], _y[7]
        unit=1, _x[8], _y[8]
        unit=2, _x[9], _y[9]
        unit=3, _x[10], _y[10]
        unit=4, _x[11], _y[11]
        unit=5, _x[12], _y[12]
        unit=6, _x[13], _y[13]
        */
        // control_checkpoints (int x, int y, int unit);
        control_checkpoints(x_[check_point[unit]+7],y_[check_point[unit]+7],unit);
        say("unit no.: "+unit+" X = "+x_[check_point[unit]+7]+" Y = "+y_[check_point[unit]+7]);
        

        // If the current checkpoint is not the same as the previous checkpoint, 
        // we have a new checkpoint, so we have to find a new path.
        IF (check_point[unit] != previous_checkpoint)
           say("checkpoint no.: "+check_point[unit]+"; previous checkpoint: "+previous_checkpoint);

           // Lets check if the current position of the enemy (X and Y) is on a black pixel,
           // the pixel pixel grid we use is 10 times smaller then the "world_map" (logicmap)
           // that the path_find() function uses. 
           // A BLACK pixel is palette color #0, and a WHITE pixel is palette color #100.
           pixel_color=100;
           pixel_color=map_get_pixel(0,world_map,x/10,y/10);
           say("pixel color: "+pixel_color);
           IF (pixel_color == 0)

               // Check if the start position is delineated, then check if the destination position is
               // also delineated.
               pixel_color=100;
               pixel_color=map_get_pixel(0,world_map,x_[check_point[unit]+7]/10,y_[check_point[unit]+7]/10);
               say("checkpoint no.: "+unit+"; X = "+x_[check_point[unit]+7]+" ; Y = "+y_[check_point[unit]+7]);
               
               IF (pixel_color == 0)
                  say("pixel color: "+pixel_color);

                  // When both positions are delineated, means that the pixel in the logic map was a BLACK pixel 
                  // (wich is not a wall), so we can look for the next checkpoint of the currrent "enemy/car".
                  say("path_find_status: "+path_find_status); 
                  path_find_status=path_find(0,world_map,x/10,y/10,x_[check_point[unit]+7]/10,y_[check_point[unit]+7]/10,0);
                  say("path_find_status: "+path_find_status);
                  
                  
                  // Update the previous checkpoint.
                  say("previous checkpoint: "+previous_checkpoint);
                  previous_checkpoint=check_point[unit];
                  say("previous checkpoint: "+previous_checkpoint+" ; unit checkpoint: "+check_point[unit]);
                  

                  // Reset all points, that are obtained with the path_getxy() function.
                  say("resetting all points");
                  FOR (counter=0;counter<257;counter++)
                      point_x[counter]=0;
                      point_y[counter]=0;
                      say("point_x["+counter+"]="+ point_x[counter]+"; point_y["+counter+"]="+point_y[counter]);
                  END

                  // When the path is found and saved in an array, we save all the points foreward.
                  // We set the first point to 1.
                  say("following point: "+following_point);
                  following_point=1;
                  say("following point: "+following_point);
                  
                  // Let's get all the points. For that, we use the path_getxty() function. This function takes the offset
                  // of two arrays (for x and y seperatly).  When path_getxy() returns a "0", it indicates that there are
                  // no more points left to come down the road.
                  IF (path_getxy_status==0)
                     say("path_getxy_status: "+path_getxy_status+" (no more points left)");
                  END
               
                  // Now the Reset to "1", so it can begin reading the points and so progresses the enemy. Indicate what 
                  // will be the first point to go, "1".   
                  point_x[0]=point_x[following_point]*10;
                  point_y[0]=point_y[following_point]*10;
                  say("following point: "+following_point);
                  say("point_x["+following_point+"]: "+point_x[following_point]+" ; point_y["+following_point+"]: "+point_y[following_point]);
               ELSE

                  // When the loop reached this section, then the ORIGIN or DESTINATION point was not within the LAYOUT, i.e.
                  // one or both are not marked in color BLACK on the logicmap used by path_find(). 
                  delete_text(text1);
                  delete_text(text2);
                  text1=write(0,0,450,0,"Checkpoint Jump! obstacle found on Checkpoint:");
                  text2=write(0,410,450,0,check_point[unit]);
                  say("Checkpoint Jump! obstacle found on Checkpoint: "+check_point[unit]);
                  check_point[unit]++;
                  IF (check_point[unit] == 8)
                     check_point[unit]=0;
                  END
               END
            END
        END
        

        // If the ENTER key was pressed the varaible "start_car" is 1, and thus the race was started.
        IF (start_car == 1)
        
           // control_checkpoints (int x, int y, int unit);
           control_checkpoints(point_x[0],point_y[0],-1);

           // Calculate the distance from the enemy to the next point_x and point_y.
           remaining_distance=fget_dist(x,y,point_x[0],point_y[0]);
           say("remaining distance between the current car and the next point: "+remaining_distance);

            // If the distance is less then 200 pixels to be indicated by the following point, but when we add the
            // value of 2 to the the "following_point" instead of 1, why do we miss a point? Simple We jumped a point because
            // if you take two continuous pixels from the logic map used by path_find(), and multiply this by 10, (remember 
            // it is 10 times smaller the logic map), we get under these pixels and we see one another, are 10 pixels in the logic map
            // was our opponents are able To move more than 10 pixels at once but no more than 20, then we skip a "point" .
            // Then the Distance between pixel and the other will be 20 pixels (of course these are not continuous, because we
            // Skipped one). Where are the enemies that are able to advance more than 10 pixels once and less than 20? If you look below 
            // you will see that "advance (enemy_velocity)" is the value of this enemy_velocity condition, and that can not be GREATER than 
            // the maximum_velocity, variable that we defined above as ... "Maximum_velocity = 18" so the most that we could move from one 
            // enemy pixel would be 18.
            IF (remaining_distance < 200)
                say("remaining distance is less then 200, increase following point by 2.");                
                following_point+=2;
                say("following point: "+following_point);

                // Check id the following point_y point_x and are not "0". When this is the case, there was very little
                // distance between one checkpoint to another and therefore did not need many points to reach the destination.
                // If there is not a "0" assigned the following point, nothing and maintain the same point as the destination.
                // 
                // Logically upon such point "step on" the next checkpoint and start again.
                // To get the last point that stuck to the next checkpoint we don't have to do anything because the last point 
                // will be glued to the next chekpoint.                
                IF (point_x[following_point] != 0 AND point_y[following_point] != 0)
                   point_x[0]=point_x[following_point]*10;
                   point_y[0]=point_y[following_point]*10;
                   say("following point: "+following_point);
                   say("point_x["+following_point+"]: "+point_x[following_point]+" ; point_y["+following_point+"]: "+point_y[following_point]);
                END
            END
          
            // Calculate the angle (angle) we should take to get to point_x and point_y, i.e. to get
            // to the next point from the current position of the enemy.
            final_angle=fget_angle(x,y,point_x[0],point_y[0]);
            say("final angle between the current car and the next point: "+final_angle);
            
            
            // This bit of code makes the "turing/rotation" of the cars more realistic.
            IF (enemy_velocity > 8)
                increment_angle=8000;
            END
            IF (enemy_velocity > 2 AND enemy_velocity < 9)
                increment_angle=4000;
            END
            IF (enemy_velocity > 10)
                angle=near_angle(angle,final_angle,increment_angle);
            END
            
            advance(enemy_velocity);
        END
        
        // If the speed of the enemy is less than the maximum they can reach, is increase it.
        IF (start_car == 1 AND enemy_velocity < maximum_velocity)
            enemy_velocity++;
        END
        FRAME;
    END // End of main loop
END // End of process



// The Process that handles each enemy's checkpoints
PROCESS int control_checkpoints (int x, int y, int unit);

PRIVATE
    int collision_id; // Stores ID of the enemy (car) process.
    
BEGIN
    ctype=c_scroll;
    graph=map_checkpoints; // The map with the filled circle that we 
                           // created earlier.
    size=50;
    
    // Check if any enemy is "stepping" the next checkpoint you touched
    collision_id=collision(TYPE enemy);
    say("own ID of this car: "+id+"; collided with car ID: "+collision_id);
    
    say("check_point unit no.: "+unit+" = "+check_point[unit]);
    
    IF (collision_id == enemy_id[unit] AND enemy_id[unit] != 0)
       check_point[unit]+=1;
       say("check_point unit no.: "+unit+" = "+check_point[unit]);
       
       // Check if the enemy pass the last checkpoint, if so resets the checkpoint
       // To re-start the loop again.
       IF (check_point[unit] == 8)
          check_point[unit]=0;
       END
    END
    FRAME; 
END




// This process shows the "search map" that path_find uses to do it's work.
PROCESS int show_search_map(int x, int y, int graph, int size, int flags);

BEGIN
    LOOP
        FRAME;
    END
END



Notes

These are the controlpoint in the "1PISTA.MAP" file, wich is the bitmap for the racetrack. This bitmap is used by the Path_find() function and has only got two colors: Black and White.

These control points are used for various things in the program.

    control point   x           y
    number
    -----------------------------------------
    0               0           0
    1               875         1126
    2               927         1262
    3               1033        1127
    4               1090        1265
    5               1194        1133
    6               1258        1267
    7               344         1124
    8               350         759
    9               590         638
    10              710         504
    11              895         356
    12              1033        731
    13              1274        932
    14              800         1136

Used in example: say(), key(), map_get_pixel(), drawing_map(), drawing_color(), draw_fcircle(), Path_find(), Path_getxy(), collision(), fget_dist(), fget_angle(), near_angle(), advance(), Array, Offset