Project:
Shiva Routing Protocol II
Author: Terry 'DS' Hendrix II
File: srp_ii.html
Purpose: Technical Specifications Documentation
Version: 0.0.1
Date: 26.02.98SRP II: Overview
The SRP
II works on the principal of partitioning a problem to
make it simpler. Instead of trying to look at every node
to make a path, I decided to partition certain nodes into
Regions to be evaluated instead. By
grouping several nodes that have two-way links into one
region, we make the problem smaller and in a simple world
lose no information. You could look at it as making
several nodes into one large reference node that holds
links to other reference nodes.
To build a path assuming
level is mapped, the AI must decide a point in 3-space as
it's path goal. Then using the closest PathNode to the AI's position and the
closest PathNode to the goal, it is possible to start
routing. We look at the AI's node's region and try to
find a direct link to the goal's region by use of Pipenodes. If not found we start to
examine the table by looking at what the region does link
to, we do a recursive search now from these links. We
continue until we find the path or the links end. If we
have a path to traverse in a region, we use it's RegionNode. I think the worst case would be
O(#R x #L) where #R = number of regions searched and #L =
number of links per region. I may be wrong.
SRP II:
Terminology
PathNode :
These hold the actual data to move from point A to B.
These could be considered at any time, but to save CPU
and RAM should only be called when the AI traverse is
traversing the region.
PipeNode:
These PathNodes are the link from region to region, and
help by giving a head and/or tail PathNode for building a
path to cross the current region to reach the goal or
subgoal. Their region id is 0, since they can not be part
of a region.
RegionNode:
The matrix of PathNodes for a certian region. These nodes
can also hold data on the region's environment.
Regions:
These are represented as a index on the RegionMapTable.
The RegionMapTable has a matrix of all the regions that
shows if they can link via a list of Pipenodes for
entry/exit of regionX to regionY. All PathNodes in a
region must have two-way links, and have the same
environment (air, water, etc.).
SRP II:
Example
Fig 1-1 An example RegionMapTable
| |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| 1 |
- |
L2-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 2 |
L1-2 |
- |
0 |
0 |
L5-2 |
0 |
0 |
L8-2 |
L9-2 |
| 3 |
0 |
0 |
- |
0 |
L5-3 |
L6-3 |
0 |
0 |
0 |
| 4 |
0 |
0 |
L3-4 |
- |
0 |
L6-4 |
L7-4 |
L8-4 |
L9-4 |
| 5 |
0 |
L2-5 |
0 |
L4-5 |
- |
0 |
0 |
0 |
L9-5 |
| 6 |
L1-6 |
0 |
L3-6 |
L4-6 |
0 |
- |
L7-6 |
0 |
0 |
| 7 |
0 |
0 |
0 |
L4-7 |
0 |
0 |
- |
L8-7 |
0 |
| 8 |
L1-8 |
L2-8 |
0 |
0 |
0 |
0 |
L7 |
- |
0 |
| 9 |
0 |
0 |
0 |
L4-9 |
0 |
L6-9 |
L7-9 |
0 |
- |
Say the
AI found itself in region 1 and wanted to go to region 7,
for a little R&R. (The AI always takes the easiest
path.)
SRP II: Recursive
Pathing Method
1.Look for direct path.
2.Skip prev regions, if you skip all the links path for
this branch DNE.
3.Walk the links, if no more links or direct path found
this branch is done.
| |
|
1 |
|
|
| |
|
1. DNE. |
|
|
| |
|
2. Skip {1}. |
|
|
| |
|
3. Walk {2, 6,
8} |
|
|
| |
2 |
6 |
8 |
|
| |
1. DNE |
DNE |
L8-7 |
|
| |
2. Skip {1, 2,
6, 8} |
Skip {1, 2, 6,
8} |
Skip {1, 2, 6,
8} |
|
| |
3. Walk {5} |
Walk{3, 4, 9} |
Path found |
|
| 5 |
|
3 |
4 |
9 |
| 1. DNE |
|
DNE |
L4-7 |
DNE |
| 2. No more
links |
|
No more links |
No more links |
No more links |
| 3. DNE |
|
DNE |
Path found |
DNE |
So two
possible paths were found: {L1-6, L6-4, L4-7} and {L1-8,
L8-7}, it must pick one by looking at distance, better
items in regions, etc. Now for the region navagation when
we start we look in the region 1 matrix for a path from
the node closest the AI to L1-6 or L1-8. The AI must call
the SRP II: RPM agian and make a subpath like {R1-3,
R3-7, R7-30, L1-6}, and then repeat this subpath routine
everytime we reach a subgoal like L1-6.
Tell me your thoughts,
stu7440@westga.edu
Terry 'DS' Hendrix II
|