AI - part 4 |
Top Previous Next |
Welcome to the fourth AI series episode! This month we have got a "real" demo that showcases the actual path finding mechanism in action.
Open the ai8.c script and run it; your screen should display an image that looks like the one below.
There are quite a few digits on the screen, but don't let that confuse you. The horizontal row will show the first 15 nodes used for the path; it's used for testing / debugging purposes, so you should disable these values in the finished version of your game. "Touched" shows the last node that was touched with the mouse, "Start" is the starting node number (the node that is the closest to the player and can see the player) and "Target" is the enemy starting point / path destination node (the one that is closest to an enemy and can see the enemy). Don't worry, we have discussed about enemies here, but they aren't present in this demo, in order to keep the code as simple as possible for now.
Did you see the player in the image above? I have moved it in the lower left corner of the screen in the image below; use the WSAD keys to control it. And before you start thinking that I'm creating an ant game here, please rest assured that the player model has a normal size, but it is placed in a big level (about 4,000 x 2,000 quants).
Time to test our demo! Click any node and you will see several blue markers showing the shortest path from the target node (the one that was clicked) and our player. Feel free to move the player anywhere in the level; you will see that the new paths are computed correctly each and every time. The upper row displays the nodes that create the correct path from the clicked node to the player.
It's one of the worst levels ever, at least in terms of placing the nodes properly, but I did that on purpose, by simply copying / pasting some level areas, rotating them, and so on; nevertheless, you will notice that the path finding algorithm does its job each time. I am using my good old Purrfect AI path finding algorithm for this demo, but I have edited the old code significantly, making it work even faster than before. Oh, and as you can probably guess, the white nodes shouldn't be visible in the final version of your game, of course; we'll make them invisible as we move closer to the end of the workshop series.
These things being said, let's start discussing the code, shall we? Since we're talking advanced AI here, we'll skip the variable declaration part and the like.
function main() { video_mode = 8; mouse_range = 15000; // the nodes can be touched even if they are 15000 quants away fps_max = 60; // limit the frame rate to 60 fps level_load(level8_wmb); wait (3); // wait for the level to be loaded camera.z = 3200; // choose a convenient camera height camera.ambient = -20; camera.tilt = -90; // and make it look down init_mouse(); while (distances_computed == 0) {wait (1);} run_algorithm(); while (1) { index %= max_nodes; // limit "index" to 0...299 in this demo if ((node_to_player[index] < closest_distance) && (see_player[index] == 1)) // if the distance from this node to the player is smaller than the current distance to the player // and we are dealing with a node that can see the player { closest_distance = node_to_player[index]; // then we have a new winner! target_node = index; // and the target is given by the current "index" value } else // haven't found a new winner? { closest_distance = node_to_player[target_node]; // then use the previous winner } index += 1; wait (1); } }
Function main sets the proper video resolution, increases the mouse touching distance to 15,000 quants, limits the frame rate to 60 fps and loads the level. We set a proper camera position, ambient and tilt angle (we want to have a bird's eye view), and then we start the mouse function. Meanwhile, other functions compute the distances between each pair of nodes, so we wait until they finish their job - our code wouldn't work properly if we don't wait until distances_computed is set to 1. Function run_algorithm is the "brain" of the AI code, computing the shortest path distance between each two nodes that are placed in the level.
The while (1) loop limits the index value to 300 (we can have up to 300 nodes / level with the current demo version). Basically, the loop tries to see if the nodes that can see the player are closer than the old node that sees the player. If new nodes are found, we have a new winner, a new value for our "Start" node. The check is done each frame, even though it could be done every 3... 5 frames; nevertheless, since we're talking about a single while (1) loop, the performance will not suffer because of this.
action player1() { VECTOR temp[3]; VECTOR movement_speed[3]; // player's movement speed var anim_percentage; // animation percentage var distance_to_ground; var time_passed = 0; player = my; // I'm the player while (1) { my.pan += 6 * (key_a - key_d) * time_step; // rotate the player using the "A" and "D" keys vec_set (temp.x, my.x); // copy player's position to temp temp.z -= 10000; // set temp.z 10000 quants below player's origin distance_to_ground = c_trace (my.x, temp.x, IGNORE_ME | USE_BOX); movement_speed.x = 15 * (key_w - key_s) * time_step; // move the player using "W" and "S" movement_speed.y = 0; // don't move sideways movement_speed.z = -(distance_to_ground - 20); // 20 = experimental value c_move (my, movement_speed.x, nullvector, IGNORE_PASSABLE | GLIDE); // move the player if (!key_w && !key_s) // the player isn't moving? { anim_percentage += 2 * time_step; // 2 = idle (stand) animation speed ent_animate(my, "idle", anim_percentage, ANM_CYCLE); } else // the player is moving? { ent_animate(my, "walk", anim_percentage, ANM_CYCLE); // play the "walk" animation anim_percentage += 8 * time_step; // 8 = "walk" animation speed } wait (1); } }
Player's code is quite simple; we rotate the player using the "A" and "D" keys and we move it using the "W" and "S" keys. The rotation speed is given by 6 and the movement speed is given by 15. We've got some gravity code as well, together with some simple walk / idle animation code.
action node() // using 30 nodes in this demo { VECTOR temp; my.emask |= (ENABLE_SCAN | ENABLE_TOUCH | ENABLE_CLICK); // every node is sensitive to scanning, touching and clicking my.event = trace_back; my.skill47 = 1234; // set this weird value for skill47 = I'm a node set (my, PASSABLE); // don't block the player or the enemies number_of_nodes += 1; // get a unique number my.skill48 = number_of_nodes; // and store it in skill48 node_coords[my.skill48][0] = my.x; // store the x and y coordinates node_coords[my.skill48][1] = my.y; // for this particular node wait (3); // wait until all the nodes are placed in the level while (current_node <= number_of_nodes) { if (current_node == my.skill48) // I'm the current node! { c_scan(my.x, my.pan, vector(360, 30, 1000), IGNORE_ME | IGNORE_WORLD | IGNORE_MAPS | SCAN_ENTS); wait (1); // not really needed, but diminishes the cpu load a bit current_node += 1; // move to the next node } wait (1); } distances_computed = 1; while (!player) {wait (1);} // wait until the player is created while (1) { node_to_player[my.skill48] = vec_dist(player.x, my.x); // store the distance to the player if (node_to_player[my.skill48] < 500) // if the player has come closer than 500 quants to this node { if (c_trace (my.x, player.x, IGNORE_ME | IGNORE_MODELS | IGNORE_PASSENTS) == 0) { see_player[my.skill48] = 1; // the node can see the player } else { see_player[my.skill48] = 0; // this node can't see the player } } wait (-0.1); // trace 10 times a second } }
The action attached to the nodes makes them sensitive to scanning, touching and clicking, running the trace_back event function when any of these events take place. We set a weird value for skill47 to uniquely identify a node (could prove to be useful in the future demos), we make the nodes passable and then we assign them an unique ID, which will be stored inside the node's own skill48.
Time to store the x and y coordinates of the node inside our node_coords array, and then wait a bit to make sure that all the nodes are placed in the level. The while loop goes through all the nodes, telling them to scan around them using an angle of 360 degrees horizontally, 30 degrees vertically and a distance of up to 1,000 quants. The distance_computed variable is set to 1 at the end of the process, and then the code waits for the player model to be loaded (should have been loaded a long time ago, but it won't hurt to take extra precautions).
The while (1) loop determines which nodes that are closer than 500 quants to the player can see the player; we don't want to kill the CPU by making it perform c_trace instructions for the nodes that are away from the player (and thus useless).
function trace_back() { if (event_type == EVENT_SCAN) { my.skill45 = handle(you); // store "you" because trace will destroy it trace_me(); } if (event_type == EVENT_TOUCH) // node touched with the mouse? { touched_node = my.skill48; // then get the number of the node that was touched with the mouse pointer } if (event_type == EVENT_CLICK) // clicked with the mouse? { start_node = my.skill48; // then this node will become start_node } }
Function trace_back is run when a node is scanned by another node or touched / clicked by the player. If the node is scanned, it will trace from its position to the scanner (take a look at the function below to see how it works), in order to determine if the scanner can see it as well. If the answer is affirmative, the current node has determined another node that is close to it and can see it, so it will use it as a potential node on the path that leads to the player whenever it is possible.
function trace_me() { wait (1); // avoid the error message dangers if (c_trace (my.x, you.x, IGNORE_ME | IGNORE_MODELS | IGNORE_PASSENTS) == 0) { you = ptr_for_handle(my.skill45); // restore the "you" pointer index = you.skill48 + my.skill48 * max_nodes; node_to_node[index] = vec_dist(my.x, you.x); } }
The function above traces from the current node to the one that has scanned it (you) and stores the distance to it if the scanner can be seen from the position of the scanned node.
function init_mouse() { mouse_map = pointer_pcx; mouse_mode = 2; while (distances_computed) {wait (1);} // enable the mouse only after all the distances were computed while (1) { if (mouse_left == 1) { display_path(); // click the left mouse button to display the path } vec_set(mouse_pos, mouse_cursor); wait (1); } }
There aren't too many things to be said about the function above; it starts doing its job when distances_computed is set to 1 and it also displays the visible path (the blue markers) when the player clicks the left mouse button.
Function run_alrorithm is probably the most important part; its first part goes through all the nodes, setting the distance between the nodes that can't see each other to 999,999. Why do we do that? Well, most nodes will be placed 100... 500 quants away from each other, and since we are interested in finding the shortest path to the player, we want to have huge values for the nodes that can't see each other, rather than the default "zero" values.
function run_algorithm() { i = 0; j = 0; while (i < max_nodes) { while (j < max_nodes) { index = j + i * max_nodes; // compute the correct index in the array if (node_to_node[index] == 0) // if these nodes can't see each other { node_to_node[index] = 999999; // set a huge distance for the nodes that can't see each other } j += 1; } i += 1; j = 0; }
This part of the function goes through all the nodes, optimizing the paths; as an example, if the distance between nodes 1 and 2 + the distance between nodes 2 and 3 is smaller than the distance between the nodes 1 and 3, then 2 is a node that belongs to a shorter path, so it should be used as a part of the winning path.
i = 0; j = 0; k = 0; while (i < max_nodes) { while (j < max_nodes) { while (k < max_nodes) // go through all the nodes { if (node_to_node[j + i * max_nodes] + node_to_node[i + k * max_nodes] < node_to_node[j + k * max_nodes]) { node_to_node[j + k * max_nodes] = node_to_node[j + i * max_nodes] + node_to_node[i + k * max_nodes]; visited[j + k * max_nodes] = i; // store the visited point } if (j == k) // dist(1,1) = dist(2,2) = dist(3,3).... = dist(299,299) should be set to 0 (not necessary but looks nicer) { node_to_node[j + k * max_nodes] = 0; // otherwise we would get d(1,1) = d(1,2) + d(2,1) if "2" is the closest node to "1" visited[j + k * max_nodes] = 0; // same thing here; the distance between a visited node and itself should be zero } k += 1; } k = 0; j += 1; } k = 0; j = 0; i += 1; } }
Function find_path finds the shortest path between any pair of nodes. As you can see, the function is very well commented, so I won't repeat the same things here.
function find_path(l, j) { i = 0; while (i < max_nodes) // search from this node for the rest of the nodes (up to 299 more nodes) { if ((i != j) && (visited[i + max_nodes * j] == 0)) // the current node can "see" these nodes, excepting itself of course (i != j) { if (node_to_node[l + max_nodes * j] == node_to_node[l + max_nodes * i] + node_to_node[i + max_nodes * j]) // that's a node on the shortest path because the shortest path includes it { k += 1; // move to the next array element path[k] = i; // and store the node number inside the array next_node = i; // store the new node on the shortest path because it will loose its value right away i = max_nodes - 1; // don't test other values - eliminate other paths that have the same length (that could happen in some levels) if (path[k] == l) // end of search, reached the starting point (l = start_node, remember?) { return; // get out of this function } } } i += 1; // increase i if the function continues to run } j = next_node; // set the next node on the path as target find_path(l, j); // recursive function, search for the shortest path again (if it searched (2,10) now search (2,9) and so on) }
Function display_path will run each time the left mouse button is pressed; this function will get the position of the winning nodes on the perfect path, displaying the blueish markers that show it.
function display_path() { VECTOR temp; proc_kill(4); // only one instance of this function is running while (mouse_left == 1) {wait (1);} // wait for the mouse button to be released k = 0; while (k < max_nodes) { path[k] = 0; // reset the array, get rid of the previously stored path k += 1; } k = 0; // start with the first element of path[30] path[k] = target_node; // write the first path element find_path(start_node, target_node); // find the shortest path between those two nodes wait (1); // wait for the path to be computed i = k; // k = number of nodes on the shortest path while (i >= 0) // decrease i until it goes below zero { temp.x = node_coords[path[i]][0]; // get the previously stored coordinates for this node temp.y = node_coords[path[i]][1]; // on x and y temp.z = -200; // and then set a decent height above the ground ent_create (path_mdl, temp, path_markers); // show the proper path from the target to the player i -= 1; } }
The function below is the one responsible for the actual display of the blue markers. As you can see, the markers are displayed for 5 seconds but you can easily change that.
function path_markers() { set (my, PASSABLE | LIGHT); my.lightrange = 0; my.blue = 255; wait (-5); // display the proper path for 5 seconds ent_remove(me); }
That's it for this month! I'll see you next time, when we'll probably have a fresh demo with a (mildly) furious enemy chasing the player. |