461 lines
14 KiB
HTML
461 lines
14 KiB
HTML
<html>
|
|
|
|
<head>
|
|
<meta http-equiv="Content-Type"
|
|
content="text/html; charset=iso-8859-1">
|
|
<meta name="GENERATOR" content="Josh Martel. Don't save this from any HTML editor other than notepad or DevStudio!">
|
|
<title>Using Smart Pathfinding Grids</title>
|
|
<style type="text/css">
|
|
<!--
|
|
|
|
body {
|
|
background-color:black;
|
|
color:white;
|
|
margin-left:12%;
|
|
margin-right:13%;
|
|
}
|
|
|
|
a {
|
|
font-weight:bold;
|
|
text-decoration:overline underline;
|
|
color:yellow;
|
|
}
|
|
|
|
a:* {
|
|
font-weight:bold;
|
|
text-decoration:none;
|
|
color:orange;
|
|
}
|
|
|
|
p {
|
|
font:12pt/16pt Arial, Geneva, sans-serif;
|
|
color:white;
|
|
margin-top:8pt;
|
|
margin-bottom:8pt;
|
|
text-indent:12pt;
|
|
}
|
|
p.firstline {
|
|
font:16pt/18pt Arial, Geneva, sans-serif;
|
|
color:blue;
|
|
}
|
|
|
|
table {
|
|
font:8pt/8pt Arial, Geneva, sans-serif;
|
|
color:white;
|
|
background:#404040;
|
|
}
|
|
|
|
ul {
|
|
font:12pt/14pt Arial, Geneva, sans-serif;
|
|
color:white;
|
|
}
|
|
|
|
ol {
|
|
font:12pt/16pt Arial, Geneva, sans-serif;
|
|
color:white;
|
|
}
|
|
|
|
h1 {
|
|
font:24pt/22pt Arial, Geneva, sans-serif;
|
|
color:orange;
|
|
text-align:center;
|
|
}
|
|
|
|
h2 {
|
|
font:18pt/18pt Arial, Geneva, sans-serif;
|
|
color:yellow;
|
|
text-align:left;
|
|
margin-top:24pt;
|
|
}
|
|
|
|
h3 {
|
|
font:14pt/14pt Arial, Geneva, sans-serif;
|
|
color:yellow;
|
|
text-align:left;
|
|
font-style:italic;
|
|
font-weight:bold;
|
|
text-decoration:underline;
|
|
margin-top:24pt;
|
|
}
|
|
|
|
pre {
|
|
font:10pt/12pt Fixedsys, Courier, serif;
|
|
background-color:#202020;
|
|
color:lightgrey;
|
|
}
|
|
|
|
code {
|
|
font:10pt/15pt Fixedsys, Courier, serif;
|
|
background-color:#202020;
|
|
color:lightgrey;
|
|
}
|
|
|
|
hr {
|
|
color:red;
|
|
margin-top:-20pt;
|
|
}
|
|
|
|
hr.h2 {
|
|
color:orange;
|
|
width:80%;
|
|
text-align:left;
|
|
}
|
|
|
|
b.red {
|
|
font:light;
|
|
color:red;
|
|
}
|
|
|
|
b.green {
|
|
font-weight:light;
|
|
color:green;
|
|
}
|
|
|
|
b.yellow {
|
|
color:yellow;
|
|
}
|
|
|
|
-->
|
|
</style>
|
|
</head>
|
|
|
|
<body>
|
|
|
|
<p align="left"><font color="#606060" size="0" face="Arial">
|
|
Last updated 8/04/2000. Don't save this from any HTML editor other than notepad or DevStudio!
|
|
</font></p>
|
|
|
|
<p> </p>
|
|
|
|
<hr>
|
|
<h1><font face="Arial">
|
|
Using "Smart Pathfinding" Grids
|
|
</font></h1>
|
|
<p> </p>
|
|
<hr>
|
|
|
|
|
|
<!--
|
|
------------------------------------------------------------------------->
|
|
|
|
<h2>Summary and Techno-Babble</h2>
|
|
<hr class=h2>
|
|
<h4>
|
|
Purpose:
|
|
</h4>
|
|
<h4>
|
|
Does smarter path-following by maintaining a set of localized grid areas
|
|
that represent an approximation of the passable terrain in that part of the map,
|
|
and using a modified form of the A* algorithm to find the best direct
|
|
path to the target.
|
|
</h4>
|
|
<p>
|
|
The grids are arrays of world coordinates and links to neighboring grid
|
|
nodes. The world coordinate represents the point in the center of the
|
|
node. The links represent entity passable transitions between nodes.
|
|
</p>
|
|
<p>
|
|
They are localized because they are confined to specific areas in the map.
|
|
The areas are defined using a special entity ("path_grid_center") which uses
|
|
it's bounding box to define the area where there should be nodes. It can
|
|
technically be placed in Ion Radiant, but in practice should only be used
|
|
in noxdrop.
|
|
</p>
|
|
<p>
|
|
Paths that have complete sections of space (e.g. two or more "path_corner"
|
|
entities) inside any grid area will automatically cause the entity following
|
|
the path to engage smart pathfinding when travelling that section of path.
|
|
</p>
|
|
<p>
|
|
Grid nodes cannot reliably move in real time once they have been processed
|
|
at level load. The only way to do it is to move the node, then use the
|
|
console command "ai_refresh", which is slow and not meant to be used often.
|
|
</p>
|
|
<p>
|
|
Invalid grid areas will be flagged as such, but still "compiled" and stored
|
|
in memory for debugging.
|
|
</p>
|
|
<h2>The Process</h2>
|
|
<hr class="h2">
|
|
|
|
<p>
|
|
What follows is an outline of the general procedure of putting a path grid in a map and making it work. Each step
|
|
that is linked is be covered in detail below. I'm assuming that you already understand
|
|
how noxdrop works so I won't bother explaining stuff that doesn't matter. Items that looks like:
|
|
</p>
|
|
<ol>
|
|
<li>] some console commands</li></b>
|
|
</ol>
|
|
<p>
|
|
are, of course, meant to be typed at the console. The detail section about that particular item should answer any
|
|
questions about the command. Just click on the number if its yellow.
|
|
</p>
|
|
|
|
<p>(load the map)<br></p>
|
|
|
|
<p>1. ] ndstart<br></p>
|
|
|
|
<p>2. ] exec noxdrop<br></p>
|
|
|
|
<p><a href="#noxdrop_ai.cfg">3.</a> ] exec noxdrop_ai <br></p>
|
|
|
|
<p>4. ] ndclass path_grid_center<br></p>
|
|
|
|
<p>5. (hit insert and create the entity)<br></p>
|
|
|
|
<p><a href="#gridsize">6.</a> ] ndsetkey gridsize xx<br></p>
|
|
|
|
<p><a href="#snap">7.</a> ] ndsnap<br></p>
|
|
|
|
<p><a href="#lowest">8.</a> ] ndsetkey lowest x<br></p>
|
|
|
|
<p><a href="#placement">9.</a> (place the box, resizing it to cover the desired area)<br></p>
|
|
|
|
<p><a href="#doublecheck">10.</a> (doublecheck that all the path_corners you wanted to enclose are blinking)<br></p>
|
|
|
|
<p>11. (if you want to test the paths and see what they look like, make a note of the
|
|
targetname or entity number of each of the path_corners you want to check out)<br></p>
|
|
|
|
<p>12. ] ndsave<br></p>
|
|
|
|
<p>13. (quit anachronox, recompile <b>-onlyents</b> the map)<font color=#808080><br></p>
|
|
|
|
<p>(the rest of the items are for when you want to test your path)</font><br></p>
|
|
|
|
<p>14. (load the map)<br></p>
|
|
|
|
<p><a href="#consoleerrors">15.</a> (check the console after loading the map, cause there may be errors or messages about your new AI grids)<br></p>
|
|
|
|
<p><a href="#ai_info2">16.</a> ] ai_info 2<br></p>
|
|
|
|
<p><a href="#griderrors">17.</a> (go to the place where your AI grid should be and check for errors)<br></p>
|
|
|
|
<p><a href="#ai_test">18.</a> (maybe use the ai_test command to see what the paths will look like)<br></p>
|
|
|
|
<h2> The Details </h2>
|
|
<hr class="h2">
|
|
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="noxdrop_ai.cfg"></a>
|
|
<h3> ]exec noxdrop_ai </h3>
|
|
<p>
|
|
This is an extra little config file that binds the keys you will use to setup the AI grids.
|
|
The keys are illustrated in the following modified screenshots. Notice that they keys were
|
|
meant to be used when looking at the grid from a specific side. If you want the keys to
|
|
do what they say you have to be in the right place, or else it might not make any sense.
|
|
But feel free to do it however you want, it will always work the same way (i.e. the 'N' key
|
|
will always expand the box along the X axis, etc). (Also, These directions assume that you
|
|
haven't rotate the entity at all (yaw = 0). "Behind" and "Left" are relative to the entity's
|
|
arrow.)
|
|
</p>
|
|
|
|
<table border="1" cellpadding="5" cellspacing="0">
|
|
<tr>
|
|
<td>
|
|
When looking at the node from the left:
|
|
</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td width=300>
|
|
<img src="x-axis_ai_noxdrop.jpg">
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<table border="1" cellpadding="5" cellspacing="0">
|
|
<tr>
|
|
<td>
|
|
When looking at the node from behind:
|
|
</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>
|
|
<img src="y-axis_ai_noxdrop.jpg">
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="gridsize"></a>
|
|
<h3> ]ndsetkey gridsize xx </h3>
|
|
<p>
|
|
Each grid has an associated gridsize. The gridsize, of course, defines how far apart the "lines" of
|
|
the grid are, and how large each grid unit is. NOTE that if an entity cannot use a grid if it's size is
|
|
smaller than the entity's bounding box size. When placing a grid you may have to do some research to
|
|
find out what the largest entity will be trying to use the grid, then make a trade off between more
|
|
grid resolution and the largest entity. Also, the larger the gridsize is and the more complex or tight
|
|
the geometry is, the more chance that there won't be a clear path available for any two path nodes.
|
|
In general, 32 is a good number. But you will need to make sure that's large enough for
|
|
whatever particular situation you're working on.
|
|
</p>
|
|
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="ndsnap"></a>
|
|
<h3> ]ndsnap </h3>
|
|
<p>
|
|
This takes the current entity and snaps it origin to lie on the nearest grid intersection. You need to
|
|
do this in order to avoid having a grid with fractional rows or columns.
|
|
</p>
|
|
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="lowest"></a>
|
|
<h3> ]ndsetkey lowest x </h3>
|
|
<p>
|
|
To understand what this means, you need to get a general idea of how the grids work. When the map starts,
|
|
the AI system searches the map for any entities named "path_grid_center". When it finds one, it takes the
|
|
entity's bounding box (the size you setup with the keys from above) and gridsize and calculates how many
|
|
elements will fit along the x and y axes. Then it creates all those grid elements (nodes) and spaces them
|
|
out in a grid along the <b class=yellow><i>top</i></b> of the bounding box. Finally it pushes each node down,
|
|
one by one, until it hits the ground. If it doesn't hit the ground or doesn't have ground under all four corners,
|
|
that node is marked as impassable.
|
|
</p>
|
|
<p>
|
|
NOW, with that in mind... if the grid entity has a "lowest" key that is non-zero, during the process
|
|
of pushing the nodes down into the ground, it will continue to push them down through the floor until it
|
|
finds the <b class=yellow><i>lowest, passable spot</i></b> that is not lower than the bottom of the bounding box. No nodes can
|
|
ever be outside the bounding box you defined.
|
|
</p>
|
|
<table border="1" cellpadding="5" cellspacing="0">
|
|
<tr>
|
|
<td>
|
|
There is a gap here because the nodes get stuck on the inclined roof and are impassable.
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<img src="lowest0.jpg">
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<table border="1" cellpadding="5" cellspacing="0">
|
|
<tr>
|
|
<td>
|
|
Now everything is OK because the nodes went all the way down to the lowest point.
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<img src="lowest1.jpg">
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="placement"></a>
|
|
<h3> (place the box, resizing it to cover the desired area) </h3>
|
|
<p>
|
|
This is pretty straighforward once you get used to the funky keys. You move the box around in the map
|
|
as you would any other entity in noxdrop. But you must use the keys from above to resize the box.
|
|
Just play with it for a while until you get a feel for it. Now stop smiling because of that dirty
|
|
joke you just thought of.
|
|
</p>
|
|
<p>
|
|
Oh, one other <b class=red>IMPORTANT NOTE</b>: if your box is just all screwed up and you just want to
|
|
start over, you can use "ndexpandbox reset" to reset the box back to the beginning position.
|
|
</p>
|
|
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="doublecheck"></a>
|
|
<h3> (doublecheck that all the path_corners you wanted to enclose are blinking) </h3>
|
|
<p>
|
|
When you have a path_grid_center selected, all the path_corners that are inside the box you defined
|
|
will blink so that you can see when they are enclosed. BEWARE, however, because it's blinking doesn't
|
|
guarantee in any way that that path_corner will have a valid path to or from it. It just means that
|
|
it will be considered inside that grid when the map starts.
|
|
</p>
|
|
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="consoleerrors"></a>
|
|
<h3> (check the console after loading the map, cause there may be errors or messages about your new AI grids) </h3>
|
|
<p>
|
|
There are three messages you should see during map load that are related to the path grids:
|
|
<pre>
|
|
AISmartpath_Init: Processing grid centered at (x,y,z)
|
|
AISmartpath_SetParameters: overriding grid size (default size) with specified (your size)
|
|
-----| AISmartpath_Init: Processed (total number of grids in the map) grids
|
|
</pre>
|
|
|
|
And there are two messages you <i> shouldn't </i> see:
|
|
<pre>
|
|
ERROR: AStar_Search got start == end
|
|
AISmartpath_Init: snapped #(entity number) (x,y,z) to grid
|
|
</pre>
|
|
|
|
</p>
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="ai_info2"></a>
|
|
<h3> ]ai_info 2 </h3>
|
|
<p>
|
|
Different levels of ai_info yeild different detail about the grid. ai_info 1 only shows paths as
|
|
lines, along with the other ai_info stuff like path corners and such. An entity's
|
|
path shows up as a thick green line (visible from the top), and the "ai_test" path
|
|
shows up as a thick purple line. ai_info 2 will show the actual valid grid nodes
|
|
and the links between them. ai_info 3 will show whatever debug info I happen to be
|
|
playing with at the time of the last publish. It might be interesting but will be
|
|
useless.
|
|
</p>
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="griderrors"></a>
|
|
<h3> (go to the place where your AI grid should be and check for errors) </h3>
|
|
<p>
|
|
Take this screenshot for example:
|
|
</p>
|
|
<table>
|
|
<tr>
|
|
<td>
|
|
<img src="lowest0.jpg">
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
<p>
|
|
The only way you would actually be able to tell that there was a gap there in your
|
|
grid (thus making that path corner in there unreachable) would be to visually check it.
|
|
</p>
|
|
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
<!---------------------------------------------->
|
|
|
|
<a name="ai_test"></a>
|
|
<h3> (maybe use the ai_test command to see what the paths will look like) </h3>
|
|
<p>
|
|
Use this command:
|
|
<pre>ai_test [edict number || targetname] [edict number || targetname]</pre>
|
|
to test paths between path_corners. If you only want to know if a path is possible, you can
|
|
do it without looking at the map at all and it will tell you when it couldn't find
|
|
a path between the two nodes you specified. When ai_info is on, however, it will draw the
|
|
path you entered so you can see exactly where it went.
|
|
</p>
|
|
|
|
</body>
|
|
</html>
|