|
|
|
This thread is locked; no one can reply to it.
|
1
2
|
| Flood Fill path finding |
|
Kris Asick
Member #1,424
July 2001
|
Neil: My project as a whole is still under wraps so once I'm well again and have the time to dive back into coding all of this I'll at least be able to report back how well whatever new method I use works out. However, I should point out that the method I recently outlined for dealing with intersections stores one direction for ALL target intersections on the map. That means if there's 200 intersections, a [200][200] array is needed to store all the potential directions to move in. The way it works is you do a flood fill for each intersection, with each node of the flood fill tracking which direction it was initially sent off in. If a node clones itself due to reaching an intersection, all cloned nodes will carry the same initial direction, while at the same time, recording that direction into the [initial_intersection][target_intersection] array index. Once the array is completely filled with directions and you run your gameplay, what you do with it is: When an entity reaches an intersection, it checks which intersection the intended target is on, or if the target is between two intersections, which of those two it's closest to. Then, you simply check the [current_intersection][target_intersection] array index to get the direction to move. When the entity hits another intersection, you simply do the same check again. In theory, this should work extremely well, and I do intend to get to implementing it once I can stop coughing every 2~5 minutes. Now, this method works as an active approach. To use it as a passive approach you would take your source intersection and your target intersection, get the initial direction, send out a pulse in that direction from the source intersection, then for each intersection reached you run the check again and continue the pulse in the direction indicated. The only trick is that because this is limited to intersections there does need to be some extra code to handle if the destination (or source) is not actually on an intersection. Destination is easier to handle, as you can pre-compute the map ahead of time to have a closest intersection ID marked on each tile. Source is a little trickier because the initial direction to move may not match up properly, in which case some extra calculations would need to be made. Plus, there also needs to be special case handling if the source intersection and destination intersection are the same, in which case it can be assumed that the real destination is close enough that simply sending pulses out in all directions will find the intended destination and thus determine the right direction to move in. --- Kris Asick (Gemini) |
|
Neil Roy
Member #2,229
April 2002
 |
I look forward to seeing your code. There's a good reason why there are path finding algorithms like Dijkstrah's (I think I finally spelled it right) and A* and nothing like what you describe. --- |
|
Kris Asick
Member #1,424
July 2001
|
Wow... OK, maybe I could just flood fill from every entity as often as needed... I just finished writing the code to pre-calc a ton of flood fills to do my intersection approach. I even threw it into its own thread with al_run_detached_thread() presuming it would take more than a moment. Apparently, all I have to do is hit the button to load the level and virtually instantly, it finishes the ENTIRE PROCESS of doing about 170 (one for each intersection in the first level) flood fills! I used the debugger to check the data stored and it actually looks like perfectly legitimate data went into the structures. The vector I used to track flood fill nodes even registered a capacity of 95, suggesting that was the most number of nodes in progress at any point in time during any flood fill. Now to alter the AI to use all of this raw data the way I intend to and see what happens... fingers crossed... EDIT: OK... my AI is now able to find me through tunnels, shoot me through tunnels, take advantage of teleporters between arbitrary points in the level and is even smart about one-way walls... I think my intersection approach is a success. The code below is for pre-calculating everything the AI needs. It's likely not going to make a lot of sense without the context of everything the game is able to do, but should be at least somewhat defining of how I'm pre-calculating my data: 1static void *_PP_PrepIntersectionMatrix_Thread (void *arg)
2{
3 std::vector<T_PP_IFF_NODE> iff_node;
4 T_PP_IFF_NODE temp_node;
5 int x, y, cx, cy, dir_ret, solid_dirs, non_solid_count, newly_entered;
6 short working_intersection;
7 bool solid_dir[4], force_spawn;
8 int floodmap[PP_MAPSIZE_X][PP_MAPSIZE_Y];
9 int z, zz;
10
11 pp_intermap->ready = false;
12 pp_intermap->intersections = 0;
13 non_solid_count = 0;
14
15 // Step 1 - Create Intertile Map and Determine All Intersections
16 for (x = 0; x < PP_MAPSIZE_X; x++) for (y = 0; y < PP_MAPSIZE_Y; y++)
17 {
18 if (pp->level.map[x][y].flags & PP_TF_SOLID)
19 pp_intermap->inter_tile[x][y] = -1;
20 else
21 {
22 solid_dirs = 0; non_solid_count++;
23 if (pp->level.MapTile(x,y-1)->IsSolid(PP_DIR_N,false)) { solid_dir[PP_DIR_N] = true; solid_dirs++; } else solid_dir[PP_DIR_N] = false;
24 if (pp->level.MapTile(x,y+1)->IsSolid(PP_DIR_S,false)) { solid_dir[PP_DIR_S] = true; solid_dirs++; } else solid_dir[PP_DIR_S] = false;
25 if (pp->level.MapTile(x+1,y)->IsSolid(PP_DIR_E,false)) { solid_dir[PP_DIR_E] = true; solid_dirs++; } else solid_dir[PP_DIR_E] = false;
26 if (pp->level.MapTile(x-1,y)->IsSolid(PP_DIR_W,false)) { solid_dir[PP_DIR_W] = true; solid_dirs++; } else solid_dir[PP_DIR_W] = false;
27 if (solid_dirs <= 1)
28 {
29 pp_intermap->inter_tile[x][y] = pp_intermap->intersections;
30 pp_intermap->inter_x[pp_intermap->intersections] = x;
31 pp_intermap->inter_y[pp_intermap->intersections] = y;
32 pp_intermap->intersections++;
33 }
34 else
35 pp_intermap->inter_tile[x][y] = -1;
36 }
37 }
38
39 // Step 2 - Determine Closest Intersections for all Tiles
40 for (x = 0; x < PP_MAPSIZE_X-1; x++) for (y = 0; y < PP_MAPSIZE_Y-1; y++) pp_intermap->inter_closest[x][y] = -1;
41 for (z = 0; z < pp_intermap->intersections; z++) pp_intermap->inter_closest[pp_intermap->inter_x[z]][pp_intermap->inter_y[z]] = z + PP_MAX_INTERSECTIONS;
42 do {
43 newly_entered = 0;
44 for (x = 0; x < PP_MAPSIZE_X; x++) for (y = 0; y < PP_MAPSIZE_Y; y++)
45 {
46 if (pp_intermap->inter_closest[x][y] >= PP_MAX_INTERSECTIONS * 2)
47 pp_intermap->inter_closest[x][y] -= PP_MAX_INTERSECTIONS; // This is protection against race conditions in the direction of scanning
48 else if (pp_intermap->inter_closest[x][y] >= PP_MAX_INTERSECTIONS)
49 {
50 pp_intermap->inter_closest[x][y] -= PP_MAX_INTERSECTIONS;
51 working_intersection = pp_intermap->inter_closest[x][y];
52 // North Check
53 cx = x; cy = y - 1; dir_ret = PP_DIR_N;
54 if (cy < 0) cy += PP_MAPSIZE_Y;
55 if (pp->level.map[cx][cy].flags & PP_TF_TELEPORTER) pp->level.teleport(cx,cy,dir_ret);
56 if (pp_intermap->inter_closest[cx][cy] < 0)
57 if (!pp->level.map[cx][cy].IsSolid(dir_ret,false))
58 { pp_intermap->inter_closest[cx][cy] = working_intersection + PP_MAX_INTERSECTIONS; newly_entered++; }
59 // South Check
60 cx = x; cy = y + 1; dir_ret = PP_DIR_S;
61 if (cy >= PP_MAPSIZE_Y) cy -= PP_MAPSIZE_Y;
62 if (pp->level.map[cx][cy].flags & PP_TF_TELEPORTER) pp->level.teleport(cx,cy,dir_ret);
63 if (pp_intermap->inter_closest[cx][cy] < 0)
64 if (!pp->level.map[cx][cy].IsSolid(dir_ret,false))
65 { pp_intermap->inter_closest[cx][cy] = working_intersection + PP_MAX_INTERSECTIONS * 2; newly_entered++; }
66 // East Check
67 cx = x + 1; cy = y; dir_ret = PP_DIR_E;
68 if (cx >= PP_MAPSIZE_X) cx -= PP_MAPSIZE_X;
69 if (pp->level.map[cx][cy].flags & PP_TF_TELEPORTER) pp->level.teleport(cx,cy,dir_ret);
70 if (pp_intermap->inter_closest[cx][cy] < 0)
71 if (!pp->level.map[cx][cy].IsSolid(dir_ret,false))
72 { pp_intermap->inter_closest[cx][cy] = working_intersection + PP_MAX_INTERSECTIONS * 2; newly_entered++; }
73 // West Check
74 cx = x - 1; cy = y; dir_ret = PP_DIR_W;
75 if (cx < 0) cx += PP_MAPSIZE_X;
76 if (pp->level.map[cx][cy].flags & PP_TF_TELEPORTER) pp->level.teleport(cx,cy,dir_ret);
77 if (pp_intermap->inter_closest[cx][cy] < 0)
78 if (!pp->level.map[cx][cy].IsSolid(dir_ret,false))
79 { pp_intermap->inter_closest[cx][cy] = working_intersection + PP_MAX_INTERSECTIONS; newly_entered++; }
80 }
81 }
82 } while (newly_entered > 0);
83
84 // Step 3 - Perform flood fill op for each intersection to determine directions of travel to other intersections
85 for (working_intersection = 0; working_intersection < pp_intermap->intersections; working_intersection++)
86 {
87 memset(floodmap,0,sizeof(floodmap));
88 iff_node.clear();
89 x = pp_intermap->inter_x[working_intersection]; y = pp_intermap->inter_y[working_intersection]; force_spawn = true;
90 do {
91 zz = (signed)iff_node.size(); if (force_spawn) zz++;
92 for (z = 0; z < zz; z++)
93 {
94 if (!force_spawn)
95 {
96 x = iff_node[z].x; y = iff_node[z].y;
97 }
98 solid_dirs = 0;
99 if (pp->level.MapTile(x,y-1)->IsSolid(PP_DIR_N,false)) { solid_dir[PP_DIR_N] = true; solid_dirs++; } else solid_dir[PP_DIR_N] = false;
100 if (pp->level.MapTile(x,y+1)->IsSolid(PP_DIR_S,false)) { solid_dir[PP_DIR_S] = true; solid_dirs++; } else solid_dir[PP_DIR_S] = false;
101 if (pp->level.MapTile(x+1,y)->IsSolid(PP_DIR_E,false)) { solid_dir[PP_DIR_E] = true; solid_dirs++; } else solid_dir[PP_DIR_E] = false;
102 if (pp->level.MapTile(x-1,y)->IsSolid(PP_DIR_W,false)) { solid_dir[PP_DIR_W] = true; solid_dirs++; } else solid_dir[PP_DIR_W] = false;
103 if (force_spawn) solid_dirs = 0;
104 switch (solid_dirs)
105 {
106 case 3: case 4: iff_node.erase(iff_node.begin()+z); z--; break;
107 case 2: {
108 if (solid_dir[iff_node[z].dir])
109 {
110 if (!solid_dir[PP_DIR_N] && PP_OPDIR[iff_node[z].dir] != PP_DIR_N) iff_node[z].dir = PP_DIR_N;
111 else if (!solid_dir[PP_DIR_S] && PP_OPDIR[iff_node[z].dir] != PP_DIR_S) iff_node[z].dir = PP_DIR_S;
112 else if (!solid_dir[PP_DIR_E] && PP_OPDIR[iff_node[z].dir] != PP_DIR_E) iff_node[z].dir = PP_DIR_E;
113 else if (!solid_dir[PP_DIR_W] && PP_OPDIR[iff_node[z].dir] != PP_DIR_W) iff_node[z].dir = PP_DIR_W;
114 }
115 floodmap[iff_node[z].x][iff_node[z].y] = 1;
116 switch (iff_node[z].dir)
117 {
118 case PP_DIR_N: iff_node[z].y--; break;
119 case PP_DIR_S: iff_node[z].y++; break;
120 case PP_DIR_E: iff_node[z].x++; break;
121 case PP_DIR_W: iff_node[z].x--; break;
122 }
123 iff_node[z].x = pp->level.map_coord_x(iff_node[z].x);
124 iff_node[z].y = pp->level.map_coord_y(iff_node[z].y);
125 if (floodmap[iff_node[z].x][iff_node[z].y] == 1) { iff_node.erase(iff_node.begin()+z); z--; break; }
126 if (pp->level.map[iff_node[z].x][iff_node[z].y].flags & PP_TF_TELEPORTER) pp->level.teleport(iff_node[z].x,iff_node[z].y,iff_node[z].dir);
127 break; }
128 case 1: case 0: {
129 floodmap[x][y] = 1;
130 // North Check
131 cx = x; cy = y - 1; dir_ret = PP_DIR_N;
132 if (cy < 0) cy += PP_MAPSIZE_Y;
133 if (pp->level.map[cx][cy].flags & PP_TF_TELEPORTER) pp->level.teleport(cx,cy,dir_ret);
134 if (!solid_dir[PP_DIR_N])
135 if (floodmap[cx][cy] != 1)
136 if (!pp->level.map[cx][cy].IsSolid(dir_ret,false))
137 {
138 temp_node.x = cx; temp_node.y = cy; temp_node.dir = dir_ret;
139 if (force_spawn) temp_node.init_dir = PP_DIR_N; else temp_node.init_dir = iff_node[z].init_dir;
140 iff_node.push_back(temp_node);
141 }
142 // South Check
143 cx = x; cy = y + 1; dir_ret = PP_DIR_S;
144 if (cy >= PP_MAPSIZE_Y) cy -= PP_MAPSIZE_Y;
145 if (pp->level.map[cx][cy].flags & PP_TF_TELEPORTER) pp->level.teleport(cx,cy,dir_ret);
146 if (!solid_dir[PP_DIR_S])
147 if (floodmap[cx][cy] != 1)
148 if (!pp->level.map[cx][cy].IsSolid(dir_ret,false))
149 {
150 temp_node.x = cx; temp_node.y = cy; temp_node.dir = dir_ret;
151 if (force_spawn) temp_node.init_dir = PP_DIR_S; else temp_node.init_dir = iff_node[z].init_dir;
152 iff_node.push_back(temp_node);
153 }
154 // East Check
155 cx = x + 1; cy = y; dir_ret = PP_DIR_E;
156 if (cx >= PP_MAPSIZE_X) cx -= PP_MAPSIZE_X;
157 if (pp->level.map[cx][cy].flags & PP_TF_TELEPORTER) pp->level.teleport(cx,cy,dir_ret);
158 if (!solid_dir[PP_DIR_E])
159 if (floodmap[cx][cy] != 1)
160 if (!pp->level.map[cx][cy].IsSolid(dir_ret,false))
161 {
162 temp_node.x = cx; temp_node.y = cy; temp_node.dir = dir_ret;
163 if (force_spawn) temp_node.init_dir = PP_DIR_E; else temp_node.init_dir = iff_node[z].init_dir;
164 iff_node.push_back(temp_node);
165 }
166 // West Check
167 cx = x - 1; cy = y; dir_ret = PP_DIR_W;
168 if (cx < 0) cx += PP_MAPSIZE_X;
169 if (pp->level.map[cx][cy].flags & PP_TF_TELEPORTER) pp->level.teleport(cx,cy,dir_ret);
170 if (!solid_dir[PP_DIR_W])
171 if (floodmap[cx][cy] != 1)
172 if (!pp->level.map[cx][cy].IsSolid(dir_ret,false))
173 {
174 temp_node.x = cx; temp_node.y = cy; temp_node.dir = dir_ret;
175 if (force_spawn) temp_node.init_dir = PP_DIR_W; else temp_node.init_dir = iff_node[z].init_dir;
176 iff_node.push_back(temp_node);
177 }
178 // Final Linking
179 if (!force_spawn)
180 {
181 pp_intermap->inter_link[working_intersection][pp_intermap->inter_tile[x][y]] = iff_node[z].init_dir;
182 iff_node.erase(iff_node.begin()+z);
183 z--;
184 }
185 else
186 force_spawn = false;
187 break; }
188 }
189 zz = (signed)iff_node.size();
190 }
191 } while (iff_node.size() > 0);
192 }
193
194 iff_node.clear();
195 pp_intermap->ready = true;
196
197 return NULL;
198}
However, this just pre-calcs all the intersections and the data to make it usable. The AI itself is very complex in this game, but it's just a single routine responsible for determining which direction to move based on the data calculated from the above code: 1int T_PP_LEVEL::CreateAITrack (int init_x, int init_y, int dest_x, int dest_y, int starting_dir, bool allow_initial_turnaround, bool inversion_field)
2{
3 // The current routine for creating AI tracks only functions if the AI is on top of an intersection. If the AI is not on an intersection, it will
4 // not alter the direction the AI is facing in.
5 int source_intersection, destination_intersection, new_dir;
6 bool exact, valid_dir[4];
7 int valid_dirs = 0;
8 int z;
9
10 GetValidDirs(init_x,init_y,valid_dir[0],valid_dir[1],valid_dir[2],valid_dir[3],inversion_field);
11 for (z = 0; z < 4; z++)
12 {
13 valid_dir[z] = !valid_dir[z];
14 if (valid_dir[z]) valid_dirs++;
15 }
16 if (!allow_initial_turnaround && valid_dirs > 1) if (valid_dir[PP_OPDIR[starting_dir]]) { valid_dir[PP_OPDIR[starting_dir]] = false; valid_dirs--; }
17 if (valid_dirs == 0) return starting_dir; // Should never happen, but let's account for it
18 if (valid_dirs == 1) { for (z = 0; z < 4; z++) if (valid_dir[z]) return z; }
19
20 if (init_x == dest_x && init_y == dest_y) goto PP_AbortAITrack; // Really, any direction works in this circumstance
21
22 source_intersection = pp_intermap->inter_tile[init_x][init_y];
23 if (source_intersection < 0) goto PP_AbortAITrack; // Can't track from a non-intersection
24
25 destination_intersection = pp_intermap->inter_tile[dest_x][dest_y];
26 if (destination_intersection >= 0)
27 exact = true;
28 else
29 {
30 exact = false;
31 destination_intersection = pp_intermap->inter_closest[dest_x][dest_y];
32 if (destination_intersection < 0) goto PP_AbortAITrack; // Doesn't appear to be a valid destination coordinate
33 }
34
35 if (source_intersection == destination_intersection)
36 {
37 // When this happens, we first try to face in a direction which makes sense, otherwise we just choose a random valid dir
38 if (init_y >= dest_y && valid_dir[PP_DIR_N]) return PP_DIR_N;
39 if (init_y <= dest_y && valid_dir[PP_DIR_S]) return PP_DIR_S;
40 if (init_x <= dest_x && valid_dir[PP_DIR_E]) return PP_DIR_E;
41 if (init_x >= dest_x && valid_dir[PP_DIR_W]) return PP_DIR_W;
42 do { z = randVal(0,3); } while (!valid_dir[z]);
43 return z;
44 }
45
46 new_dir = pp_intermap->inter_link[source_intersection][destination_intersection];
47 if (valid_dir[new_dir]) return new_dir;
48
49 PP_AbortAITrack:
50
51 do { z = randVal(0,3); } while (!valid_dir[z]);
52 return z;
53}
Yeah, again, without a TON of context this code isn't going to make TOO much sense, but just trust me when I say, it's working a Hell of a lot better than what I was previously doing! EDIT (The Next Day): Just a heads-up if anyone wants to use the code above: It's got some bugs I've been fixing over the course of the day, such as creating multiple nodes on top of one another as well as new nodes technically moving a single tile faster than they're supposed to, plus I had to add a special condition for dealing with moving through one-way walls directly into a corner as the code above would simply keep moving in a valid direction instead of creating two new nodes like it should to go both ways out from the corner. All that said though, it's been working pretty darn well. The AI's been performing some extremely smart moves, especially in regards to tunnels, and it's kinda scary... BTW: The game I'm working on right now is the second of the first three which will be included with my project for free, so you'll all get to see this code in action soon enough, probably in the next couple months. --- Kris Asick (Gemini) |
|
Neil Roy
Member #2,229
April 2002
|
That's awesome! Nice to see you got something working. That's a nice solution, for smaller levels, just calculating at nodes at runtime is a nice idea. It nice to have the AI in there. I may still experiment with some of the other algorithms, I have been reading on some other ideas, maybe try A* again, see if that makes a difference at all. Some other code I played around with is code to generate random levels (mazes) using a few ideas. I am thinking about tweaking it and seeing what I can come up with for level generation for my existing games. --- |
|
|
1
2
|
I think you guys are in for a surprise.
