Great Wanderer
 |
Note: Some formulas used here are using the Mediawiki-maths system. They show up fine on the WaS wiki where we write our articles but, for now, they may not display properly on the Second Life wiki. |
Created by Kira Komarov, tertiary adjunct of the Wizardry and Steamworks matrix.
Introduction
As we have previously discussed weighted state machines Wizardry and Steamworks/State Machines, we provide an example of what the weighted non-deterministic finite automaton (wNFA) might be be used for. We name it Great Wanderer since it is an similar to Wanderer but provides proximity-aware movement.
More precisely, a usual variation of Wanderer is to add the following lines at the end of the code:
collision_start(integer num)
{
moveTo(nextCoordinates(MOVEMENT_TYPE));
}
which would make the wandering object change its destination in case it collides with another object.
The Great Wanderer, on the other hand, uses the wNFA to probabilistically determine the next destination.
YouTube Video
<videoflash>Uet6amLjuHk</videoflash>
Theory
This implementation is based on two former articles published by Wizardry and Steamworks:
- Please see our original article Wizardry and Steamworks/State Machines, for what we have defined as a Weighted Non-Deterministic Finite Automaton (wNFA).
- Also, please see Wizardry and Steamworks/Randomness, Entropy and Statistics for an introduction to cumulative probabilities.
- Additionally, for extracting data from Second Life, for the cartography example, we use a modified version of Permanent Primitive URL which was also previously used in Wizardry and Steamworks/Population Genetics and Selection to pull and display allele frequencies on a pie chart. This time, we need a 3D plotter, that will allow us to feed a tuple vector, representing the current location of the Great Wanderer and obtain a 3D graph.
wNNA
As you can observe from Figure 1., the Great Wanderer uses the following states to navigate an enclosed space:
default - this is the initial state. forward - move the great wanderer forward. backward - move the great wanderer backward. left - move the great wanderer left. right - move the great wanderer right. up - move the great wanderer up. down - move the great wanderer down. compute - reserved for event protection.
The difference from our classic wNFA is that we do not consume states. Instead, they are re-used again, depending on the changes in probabilities for every movement: forward, backward, left, right, up and down. That makes it a Weighted Non-Deterministic Non-Finite Automaton (wNNA) rather, since the Great Wanderer never stops moving and hence never ends up in an end-state. This is on purpose because the Great Wanderer is not meant to stop moving at any point.
Furthermore, we ensure that we do not get stuck in some state by using a timer in each state:
timer()
{
llSetTimerEvent((float)FALSE);
vector velocity = llList2Vector(llGetObjectDetails(llGetKey(), [OBJECT_VELOCITY]), 0);
if(llFabs(llVecMag(velocity)) < ENGINE_SPEED/2)
state compute;
llSetTimerEvent(1.0);
}
which ensures that in case the velocity of the Great Wanderer drops to less than half of the engine speed, the wNNA will immediately switch to the recompute state which will first decrement the probability of the current direction being chosen (since it got the Great Wanderer stuck in the first place) and then pick a new direction based on the current amended set of probabilities.
Formally, a wNNA is a reduction of a wNFA where the set of final (accepting) states is empty (<math>F=( \Phi )</math>). An extra condition is that all the probabilities have to add up to the same value at every transition of the automaton: <math> P_{t} = p_{f} + p_{b} + p_{l} + p_{r} + p_{u} + p_{d} </math> In other words, <math>P_{t}</math> must remain constant for all transitions of the wNNA (see Figure 1.). In this script, we have chosen probabilities in the range <math>[0,1)</math> for convenience.
Cancelling Gravity
The default state is the main entry point, and used for initial set-up. In the default we set-up the counter-gravity by calling llSetBuoyancy with a parameter of 1. It might be (although it is unspecified), that in some cases llSetForce is inappropriate for countering gravity unless the distance between the Great Wanderer and the earth is taken into consideration. That is, when we tested llSetForce by calling:
llSetForce(<0,0,9.81>*llGetMass(), FALSE);
we noticed undefined behaviour. Our first tests, consisted in a physical primitive containing the aforementioned code, placed within a physical and hollow box which resulted in the upward force being larger than -G, resulting in some unexplained upward movement. Conversely, when not in an enclosed environment, the physical box manifested expected behaviour. Because of that, we switched to llSetBuoyancy which, for now, results in the expected result.
As you can see from Figure 1., the default state switches directly to the compute state in order to calculate the next direction of movement. That is where we use llSetBuoyancy to cancel out all the gravity.
Simplified Algorithm
The movement of the Great Wanderer is given by the following algorithm:
- initially pick some direction d to move on based on the set of probabilities P.
- if there is a collision at some point on the trajectory given by the direction d
- lower the probability of that direction being chosen again by decrementing it and redistributing the remainder to the rest of the probabilities P evenly.
- random-cumulatively pick the next the direction d based on the amended set of probabilities P.
- move on the trajectory given by the new direction d.
- repeat at 2.
Thurst and Anti-Thrust
For thrust-control, we use two functions: one function that sets the velocity of the object (although impulse would also be feasible) based on the direction d and another function that reverses the velocity. We named them intuitively thrust and anti-thrust:
// Thrust and anti-thrust corrections based on current movmement.
// ENGINE_SPEED - the velocity in m/s that the Great Wanderer will move at.
float ENGINE_SPEED = 0.1;
// Thurst and anti-thrust: anti-thrust = -thrust.
// Thrust. Set velocity corresponding to x,y,z-axis.
thrust(string direction)
{
if (direction == "forward")
llSetVelocity(<0,0,ENGINE_SPEED>, TRUE);
else if (direction == "backward")
llSetVelocity(<0,0,-ENGINE_SPEED>, TRUE);
else if (direction == "left")
llSetVelocity(<ENGINE_SPEED,0,0>, TRUE);
else if (direction == "right")
llSetVelocity(<-ENGINE_SPEED,0,0>, TRUE);
else if (direction == "up")
llSetVelocity(<0,ENGINE_SPEED,0>, TRUE);
else if (direction == "down")
llSetVelocity(<0,-ENGINE_SPEED,0>, TRUE);
}
anti_thrust(string direction)
{
if (direction == "forward")
llSetVelocity(<0,0,-ENGINE_SPEED>, TRUE);
else if (direction == "backward")
llSetVelocity(<0,0,ENGINE_SPEED>, TRUE);
else if (direction == "left")
llSetVelocity(<-ENGINE_SPEED,0,0>, TRUE);
else if (direction == "right")
llSetVelocity(<ENGINE_SPEED,0,0>, TRUE);
else if (direction == "up")
llSetVelocity(<0,-ENGINE_SPEED,0>, TRUE);
else if (direction == "down")
llSetVelocity(<0,ENGINE_SPEED,0>, TRUE);
}
Although this gives an instantaneous velocity, which would not otherwise be possible, the algorithm still allows the use of llApplyImpulse. For examples sake, we have chosen llSetVelocity since it reduces the calculations for counter-forces.
Possible Practical Applications
Possibly, except animating animals in Second Life, the Great Wanderer could be used for autonomous space exploration; one result thereof could be passively cartographing that space. This works well under Second Life terms (see below), however under real-life circumstances one may not wish to collide with an object in order to sense that that object is in the path of the current trajectory.
In such circumstances, similar to Second Life, one could use a detector (llSensor) that continuously scans a <math>2*\Pi</math> area, encompassing the entire volume of the Great Wanderer and switch to the compute state once the proximity of an object has been detected. This would avoid collisions but for simplicity's sake, we avoided to complicate the example since there is no destruction due to impact in Second Life (although implementing it would be easy with Great Wanderer, simply by progressively darkening the faces on impact but without the possibility of elastic deformations).
Cartography
Since the Great Wanderer is able to sense and repel from objects and determines the next destination by calculating the safest route based on the cumulative probabilities of all directions, a practical application could be to use the Great Wanderer for space mapping. More precisely, given an enclosed space (cubic, under simulation restrictions), the Great Wanderer will eventually explore all the possible areas of the cube. Whenever the Great Wanderer impacts with a primitive, the Great Wanderer's coordinates are recorded in a database. After that, all the coordinates gathered by Wanderer are mapped in three dimensions.
Given an uniform scattering of probabilities, eventually every point within the confined space will be visited at some point.
Cartography: Great Wanderer One Real-Time Collisions
Great Wanderer One is the name given to a Great Wanderer, currently at the University of New Orleans which is currently mapping a 5m by 5m by 5m box (inexactly, as we were too lazy to measure the box properly). The dimensions of the Great Wanderer One are 0.5m by 0.5m by 0.5m.
The Great Wanderer uses this page to in-line a 3D scatter plot based on the Iframe Widget which does not work on the Second Life wiki. We keep this template reserved in case the iframe widget will be re-enabled. You can access the external link here.
One may observe that the most dense scatter on the real-time display, takes place around corners and close objects. This is because the wNNA has to do the most work around those difficult geometries. You can observe a typical corner-movement in the YouTube video posted above.
Preliminary graph observations:
The graph looks rotated compared to the image in the video, perhaps something to do with the local axes being different and asking for llGetPos. The right part of the cuboid seems to be z (not sure, needs more data).One of those free mouse-drag-and-rotate graphs would be cool, gnuplot gives major headaches.
- The very first observation that we can make is that the Great Wanderer finds itself in a cuboid-shaped enclosure. The extreme collision-cloud formations join up, being quite parallel to the axes.
- Based on the former, we can preliminarily conclude that the cuboid is resting on flat ground. That is, the ground underneath the enclosure is flat.
- From the graph, we can see that the cage (see YouTube video) is placed approximately at 24.5 meters above the water level (the z-axis gives that away).
- We can observe that the box indeed spans approximately 5m on all three axes:
For x:
<math>36-31.5 = 4.5m</math>.
For z:
<math>29-24.5=4.5m</math>.
For y:
<math>48-43.5=4.5m</math>.
Which is pretty close to a cube (particular case of a cuboid). Makes sense, I just jammed the walls in and did not care to much about creating a perfect 5x5x5 cube. By jamming them in, I probably reduced the dimensions by 0.5m, getting close to the 4.5m from our calculations.
- Furthermore, the cloud formation in the bottom right corner on the graph at approx <math>(36,47.5,24.5)</math>, if you look at it closely, almost gives the contour of the corner. :-)
- The coordinates, along the x-axis of the graph are growing and the coordinates along the y-axis are growing as well. That means that the box is positioned with the bottom left corner (close to 31.5 value on the bottom left part of the graph) towards the region's origin <math>(0,0,0)</math>.
- Based on the former, we know the box is positioned approximately 31.5mx43.5m away from the region's origin <math>(0,0,0)</math>.
- Based on the former, the enclosure is facing North with its top forward face (the unmarked scale, not the one one the left).
- We have two cloud-formations in the middle, hinting that we have objects on the interior of the enclosure with which the Great Wanderer collided a few times.
Code
The Great Wanderer, has four modules which one may use independently, depending on the application:
- [K] Great Wanderer - the main engine.
- [K] Pos2DB - a script to post collisions to a database.
- A PHP script to insert coordinates into a database.
- A HTML-jQuery script to refresh an image.
The [K] Pos2DB, the PHP script and the HTML-jQuery are all optional. They are only needed in case one chooses to track the Great Wanderer.
Code: [K] Great Wanderer
//////////////////////////////////////////////////////////
// [K] Kira Komarov - 2011, License: GPLv3 //
// License at: http://www.gnu.org/licenses/gpl.html //
//////////////////////////////////////////////////////////
// A quicksort, providing a stable map between two sets of elements.
// Set a = ( a, b, c, d, e )
// Set b = ( 6, 1, 7, 3, 2 )
// Result: Set c = ( 1, b, 2, e, 3, d, 6, a, 7, c )
list dualQuicksort(list a, list b) {
if(llGetListLength(a) <= 1) return a+b;
float pivot_a = llList2Float(a, llGetListLength(a)/2);
string pivot_b = llList2String(b, llGetListLength(b)/2);
a = llDeleteSubList(a, llGetListLength(a)/2, llGetListLength(a)/2);
b = llDeleteSubList(b, llGetListLength(b)/2, llGetListLength(b)/2);
list less = [];
list less_b = [];
list more = [];
list more_b = [];
integer i = 0;
do {
if(llList2Float(a, i) > pivot_a)
{
less += llList2List(a, i, i);
less_b += llList2List(b, i, i);
}
else
{
more += llList2List(a, i, i);
more_b += llList2List(b, i, i);
}
} while(++i<llGetListLength(a)*2);
return dualQuicksort(less, less_b) + [ pivot_a ] + [ pivot_b ] + dualQuicksort(more, more_b);
}
// (the clever bit) wNNA and weighted probabilities algorithm that
// calculate the next state of the wNFA based on every state's weight
// The amount by which every weight's probability will be decreased
// in case of a collision.
float CORRECTION_AFFINITY = 0.2;
// (the clever bit) wNNA
string getNextState(string current_state) {
integer idx = llListFindList(qD, (list)current_state);
float diff = 0;
float pIdx = llList2Float(QT, idx);
if(pIdx <= CORRECTION_AFFINITY) {
diff = CORRECTION_AFFINITY-pIdx;
pIdx = 0;
}
else {
pIdx = pIdx - CORRECTION_AFFINITY;
}
QT = llListReplaceList(QT, (list)pIdx, idx, idx);
integer itra = llGetListLength(QT)-1;
do {
if(itra != idx) {
QT = llListReplaceList(QT, (list)(llList2Float(QT, itra)+(CORRECTION_AFFINITY-diff)/5.0), itra, itra);
}
} while(--itra>=0);
//DEBUG - Uncomment for probability debug.
//llOwnerSay("Directions: " + llDumpList2String(qD, " ") + "\nProbabilities: " + llDumpList2String(QT, " "));
//llOwnerSay("Probabilities add up to: " + (string)llListStatistics(LIST_STAT_SUM, QT));
// Now, compute next hop based on the highest probability in the list.
list P = dualQuicksort(QT, qD);
list dirs = llList2ListStrided(llDeleteSubList(P, 0, 0), 0, llGetListLength(P)-1, 2);
list dirs_prob = llList2ListStrided(P, 0, llGetListLength(P)-1, 2);
//DEBUG - Uncomment for probability debug.
//llOwnerSay("\Probabilities add up to: " + (string)llListStatistics(LIST_STAT_SUM, QT) + "\nSorted probabilities: " + llDumpList2String(P, ","));
float rnd = llFrand(1);
float cum = 0;
itra=llGetListLength(dirs_prob)-1;
do {
cum += llList2Float(dirs_prob, itra);
if(cum >= rnd) {
if(llList2String(dirs, itra) == "forward") return "forward";
if(llList2String(dirs, itra) == "backward") return "backward";
if(llList2String(dirs, itra) == "left") return "left";
if(llList2String(dirs, itra) == "right") return "right";
if(llList2String(dirs, itra) == "up") return "up";
if(llList2String(dirs, itra) == "down") return "down";
}
} while(--itra>=0);
// This should not happen.
return "ERROR";
}
// Thrust and anti-thrust corrections based on current movmement.
// ENGINE_SPEED - the velocity in m/s that the Great Wanderer will move at.
float ENGINE_SPEED = 0.1;
// Thurst and anti-thrust: anti-thrust = -thrust.
// Thrust. Set velocity corresponding to x,y,z-axis.
thrust(string direction) {
// My kingdom for a switch.
if(direction == "forward") { llApplyImpulse(<0,0,ENGINE_SPEED/llGetMass()>, TRUE); return; }
if(direction == "backward") { llApplyImpulse(<0,0,-ENGINE_SPEED/llGetMass()>, TRUE); return; }
if(direction == "left") { llApplyImpulse(<ENGINE_SPEED/llGetMass(),0,0>, TRUE); return; }
if(direction == "right") { llApplyImpulse(<-ENGINE_SPEED/llGetMass(),0,0>, TRUE); return; }
if(direction == "up") { llApplyImpulse(<0,ENGINE_SPEED/llGetMass(),0>, TRUE); return; }
if(direction == "down") { llApplyImpulse(<0,-ENGINE_SPEED/llGetMass(),0>, TRUE); return; }
}
// Anti-thrust. Reverses all velocities on x,y,z-axis.
anti_thrust(string direction) {
// My switch for a kingdom.
if(direction == "forward") { llApplyImpulse(<0,0,-ENGINE_SPEED/llGetMass()>, TRUE); return; }
if(direction == "backward") { llApplyImpulse(<0,0,ENGINE_SPEED/llGetMass()>, TRUE); return; }
if(direction == "left") { llApplyImpulse(<-ENGINE_SPEED/llGetMass(),0,0>, TRUE); return; }
if(direction == "right") { llApplyImpulse(<ENGINE_SPEED/llGetMass(),0,0>, TRUE); return; }
if(direction == "up") { llApplyImpulse(<0,-ENGINE_SPEED/llGetMass(),0>, TRUE); return; }
if(direction == "down") { llApplyImpulse(<0,ENGINE_SPEED/llGetMass(),0>, TRUE); return; }
}
// wNFA States corresponding to directions.
list qD = [ "forward", "backward", "left", "right", "up", "down" ];
// wNFA Weights for each direction. Must add up to 1.0.
// assert: length(qD) == length(QT)
list QT = [ 0.15, 0.17, 0.17, 0.17, 0.17, 0.17 ];
string nextState = "";
string currentState = "";
// These are simulation limits. The prim could travel
// higher, perhaps even crossing sim borders but it may
// be hard to find feel free to extend these limits.
//
// latitude
// +--------+
// | | longitude
// +--------+
//
// Each region can be represented as a square title on
// a sphere. Thus, the latitude runs along the x-axis
// and the latitude along the y-axis.
integer MAX_ALTITUDE = 254;
integer MAX_LONGITUDE = 254;
integer MAX_LATITUDE = 254;
// Minimal distance delta that will let the object
// consider itself as being stationary and compute
// the next direction in which it should travel.
float MIN_DELTA_STATIONARY = 0.1;
// Maximum velocity over which the Great Wanderer should not travel.
// Added since llSetVelocity has been changed to llApplyImpulse.
float MAX_VELOCITY = 1.0;
vector oPos = ZERO_VECTOR;
default
{
state_entry()
{
oPos = llGetPos();
// Ok, yeah -G is not always an option, especially when
// the distance between masses is large enough to topple
// the fraction. Let's just assume we're in space, earth
// is relatively boring.
llSetStatus(STATUS_PHYSICS, FALSE);
llSetStatus(STATUS_PHYSICS, TRUE);
llSetBuoyancy(1.0);
// None of that. Yet.
llSetStatus(STATUS_ROTATE_X|STATUS_ROTATE_Y|STATUS_ROTATE_Z, FALSE);
// Now, compute next hop based on the highest probability in the list
// and switch to first state, forward, backward, left, right, up or down.
list P = dualQuicksort(QT, qD);
list dirs = llList2ListStrided(llDeleteSubList(P, 0, 0), 0, llGetListLength(P)-1, 2);
list dirs_prob = llList2ListStrided(P, 0, llGetListLength(P)-1, 2);
float rnd = llFrand(1);
float cum = 0;
integer itra=llGetListLength(dirs)-1;
do {
cum += llList2Float(dirs_prob, itra);
if(cum >= rnd) {
if(llList2String(dirs, itra) == "forward") state forward;
if(llList2String(dirs, itra) == "backward") state backward;
if(llList2String(dirs, itra) == "left") state left;
if(llList2String(dirs, itra) == "right") state right;
if(llList2String(dirs, itra) == "up") state up;
if(llList2String(dirs, itra) == "down") state down;
}
} while(--itra>=0);
}
}
state forward
{
state_entry() {
// DEBUG movement.
//llOwnerSay("moving foward");
currentState = "forward";
thrust(currentState);
llSetTimerEvent(2); // Anti-stuck.
}
collision_start(integer num) {
state compute;
}
timer() {
llSetTimerEvent(0);
if(llVecDist(oPos, llGetPos()) < MIN_DELTA_STATIONARY) {
oPos = llGetPos();
state compute;
}
if(oPos.x > MAX_LATITUDE || oPos.y > MAX_LONGITUDE || oPos.z > MAX_ALTITUDE) state compute;
if(llFabs(llVecMag(llList2Vector(llGetObjectDetails(llGetKey(), [OBJECT_VELOCITY]), 0))) < MAX_VELOCITY) jump nothrust;
thrust(currentState);
@nothrust;
llSetTimerEvent(1);
}
}
state backward
{
state_entry() {
// DEBUG movement.
//llOwnerSay("moving backward");
currentState = "backward";
thrust(currentState);
llSetTimerEvent(2); // Anti-stuck.
}
collision_start(integer num) {
state compute;
}
timer() {
llSetTimerEvent(0);
if(llVecDist(oPos, llGetPos()) < MIN_DELTA_STATIONARY) {
oPos = llGetPos();
state compute;
}
if(oPos.x > MAX_LATITUDE || oPos.y > MAX_LONGITUDE || oPos.z > MAX_ALTITUDE) state compute;
if(llFabs(llVecMag(llList2Vector(llGetObjectDetails(llGetKey(), [OBJECT_VELOCITY]), 0))) < MAX_VELOCITY) jump nothrust;
thrust(currentState);
@nothrust;
llSetTimerEvent(1);
}
}
state left
{
state_entry() {
// DEBUG movement.
//llOwnerSay("moving left");
currentState = "left";
thrust(currentState);
llSetTimerEvent(2); // Anti-stuck.
}
collision_start(integer num) {
state compute;
}
timer() {
llSetTimerEvent(0);
if(llVecDist(oPos, llGetPos()) < MIN_DELTA_STATIONARY) {
oPos = llGetPos();
state compute;
}
if(oPos.x > MAX_LATITUDE || oPos.y > MAX_LONGITUDE || oPos.z > MAX_ALTITUDE) state compute;
if(llFabs(llVecMag(llList2Vector(llGetObjectDetails(llGetKey(), [OBJECT_VELOCITY]), 0))) < MAX_VELOCITY) jump nothrust;
thrust(currentState);
@nothrust;
llSetTimerEvent(1);
}
}
state right
{
state_entry() {
// DEBUG movement.
//llOwnerSay("moving right");
currentState = "right";
thrust(currentState);
llSetTimerEvent(2); // Anti-stuck.
}
collision_start(integer num) {
state compute;
}
timer() {
llSetTimerEvent(0);
if(llVecDist(oPos, llGetPos()) < MIN_DELTA_STATIONARY) {
oPos = llGetPos();
state compute;
}
if(oPos.x > MAX_LATITUDE || oPos.y > MAX_LONGITUDE || oPos.z > MAX_ALTITUDE) state compute;
if(llFabs(llVecMag(llList2Vector(llGetObjectDetails(llGetKey(), [OBJECT_VELOCITY]), 0))) < MAX_VELOCITY) jump nothrust;
thrust(currentState);
@nothrust;
llSetTimerEvent(1);
}
}
state up
{
state_entry() {
// DEBUG movement.
//llOwnerSay("moving up");
currentState = "up";
thrust(currentState);
llSetTimerEvent(2); // Anti-stuck.
}
collision_start(integer num) {
state compute;
}
timer() {
llSetTimerEvent(0);
if(llVecDist(oPos, llGetPos()) < MIN_DELTA_STATIONARY) {
oPos = llGetPos();
state compute;
}
if(oPos.x > MAX_LATITUDE || oPos.y > MAX_LONGITUDE || oPos.z > MAX_ALTITUDE) state compute;
if(llFabs(llVecMag(llList2Vector(llGetObjectDetails(llGetKey(), [OBJECT_VELOCITY]), 0))) < MAX_VELOCITY) jump nothrust;
thrust(currentState);
@nothrust;
llSetTimerEvent(1);
}
}
state down
{
state_entry() {
// DEBUG movement.
//llOwnerSay("moving down");
currentState = "down";
thrust(currentState);
llSetTimerEvent(2); // Anti-stuck.
}
collision_start(integer num) {
state compute;
}
timer() {
llSetTimerEvent(0);
if(llVecDist(oPos, llGetPos()) < MIN_DELTA_STATIONARY) {
oPos = llGetPos();
state compute;
}
if(oPos.x > MAX_LATITUDE || oPos.y > MAX_LONGITUDE || oPos.z > MAX_ALTITUDE) state compute;
if(llFabs(llVecMag(llList2Vector(llGetObjectDetails(llGetKey(), [OBJECT_VELOCITY]), 0))) < MAX_VELOCITY) jump nothrust;
thrust(currentState);
@nothrust;
llSetTimerEvent(1);
}
}
state compute
{
state_entry() {
llOwnerSay(currentState);
anti_thrust(currentState);
// TRACKER comment the next line if not needed.
llMessageLinked(LINK_THIS, 0, (string)llGetPos(), "");
nextState = getNextState(currentState);
llSetTimerEvent(1);
}
timer() {
llSetTimerEvent(0);
@retry;
if(nextState == currentState) {
nextState = getNextState(currentState);
jump retry;
}
//DEBUG previous and next states.
//llOwnerSay("prev: " + currentState);
//llOwnerSay("next: " + nextState);
if(nextState == "forward") state forward;
if(nextState == "backward") state backward;
if(nextState == "left") state left;
if(nextState == "right") state right;
if(nextState == "up") state up;
if(nextState == "down") state down;
}
}
Code: [K] Pos2DB
//////////////////////////////////////////////////////////
// [K] Kira Komarov - 2011, License: GPLv3 //
// License at: http://www.gnu.org/licenses/gpl.html //
//////////////////////////////////////////////////////////
key pReq = NULL_KEY;
default
{
link_message(integer sender_num, integer num, string str, key id)
{
list pl = llParseString2List(str, ["<", ">", ","], []);
pReq = llHTTPRequest("http://was.fm/gw.php?login=kk&apiKey=ef13f100ce&point="
+ llList2String(pl,0) + ","
+ llList2String(pl,1) + ","
+ llList2String(pl,2), [], "");
}
http_response(key request_id, integer status, list metadata, string body)
{
if(request_id == pReq)
{
pReq = NULL_KEY;
if(body != "PACK")
llOwnerSay("Insert error.");
}
}
}
Code: Server, PHP Component
This code relies on a script called PHP_GnuPlot.php written by Eric Liu Yi which allows us to represent data graphically using GNU Plot.
The backend is a MySQL type database, storing data in a table data_one and using a table that you may generate with: <sql> DROP TABLE IF EXISTS `data_one`; CREATE TABLE `data_one` (
`x` float NOT NULL, `y` float NOT NULL, `z` float NOT NULL, `id` int(10) unsigned NOT NULL auto_increment, PRIMARY KEY (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=405 DEFAULT CHARSET=latin1; </sql>
The PHP script is used to insert the data into database, filling rows of x, y and z and incrementing id on every insertion. We have chosen to maintain an auto-incrementing index id for every row, in case we would like to replay the trajectory and track the path that the Great Wanderer followed by looking at the collisions.
<php> <?php
require('PHP_GnuPlot.php');
var DATABASE_HOST = ; // Fill me in. var DATABASE_USERNAME = ; // Fill me in. var DATABASE_PASSWORD = ; // Fill me in. var DATABASE_NAME = ; // Fill me in.
// Insert simulator URL if the user has authed.
if(isset($_GET['login']) && isset($_GET['apiKey'])) {
// Authentication.
if($_GET['login'] == 'kk' && $_GET['apiKey'] == 'ef13f100ce') {
// We got a collision.
if(isset($_GET['point'])) {
$point = $_GET['point'];
$pa = str_getcsv($point);
$link = mysql_connect($DATABASE_HOST, $DATABASE_USER, $DATABASE_PASSWORD);
if(!$link) {
print 'Sorry, a database connection could not be established.';
return;
}
mysql_select_db($DATABASE_NAME, $link);
$query = sprintf("INSERT INTO data_one(x,y,z) VALUES('%s', '%s', '%s')",
mysql_real_escape_string($pa[0], $link),
mysql_real_escape_string($pa[1], $link),
mysql_real_escape_string($pa[2], $link));
mysql_query($query, $link);
mysql_close($link);
print "PACK";
return;
}
}
}
// Connect to database and fetch data and add it to graph.
$p = new GNUPlot();
$data = new PGData('collision');
$link = mysql_connect($DATABASE_HOST, $DATABASE_USER, $DATABASE_PASSWORD);
if(!$link) {
print 'Sorry, a database connection could not be established.';
return;
}
mysql_select_db($DATABASE_NAME, $link);
$query = 'SELECT * FROM data_one';
$queryResult = mysql_query($query, $link);
$itra = 0;
$rows = mysql_num_rows($queryResult);
while($itra < $rows) {
$x = mysql_result($queryResult, $itra, 'x');
$y = mysql_result($queryResult, $itra, 'y');
$z = mysql_result($queryResult, $itra, 'z');
$data->addDataEntry( array($x, $y, $z) );
$itra++;
}
mysql_close($link);
header('Content-Type: image/png');
$p->setTitle("Great Wanderer One: ".$rows." collisions");
$p->splotData( $data, 'points', '1:2:3' );
$p->set("autoscale");
$p->export('gw.png');
$p->close();
$im = imagecreatefrompng('gw.png');
imagepng($im);
exit;
?> </php>
Code: Server, HTML-jQuery Component
The HTML-jquery part, is a jQuery wrapper that reloads the chart every few seconds. It is based originally on a jQuery div refresh which we used before for the Wizardry and Steamworks/Population Genetics and Selection article.
<html4strict> <html> <head> <script type="text/javascript" src="jquery.js"></script> <script type="text/javascript">
$(document).ready(function() {
$("#gw").load("gw.php");
var refreshId = setInterval(function() {
$("#gw").attr("src", "gw.php?d="+ new Date().getTime());
}, 10000);
$.ajaxSetup({ cache: false });
}); </script> </head> <body> <img id="gw" src="gw.php" /> </body> </html> </html4strict>
Conditioned Probabilistic Pathfinding
Now that we have established an array of probabilities that is used to compute the next waypoint for the great wanderer, we can spray the array at any point in order to condition the direction of movement. We keep in mind that the great wanderer uses a probabilistic decrease of each direction once a collision occurs along an axis and use the same technique in order to condition the overall movement of the great wanderer in order to reach a certain set of coordinates.
The advantage of this method, of spraying the array of probabilities is that we impose an overall tendency concerning the movement of the great wanderer and by doing that we still allow some leniency for the great wanderer to avoid objects by performing course corrections. In that sense, the array of probabilities is conditioned by by two factors:
- the collision-based probability spray.
- the overall direction-based probability spray.
In the last chapter, we have described the first case in which the array of probabilities is altered dynamically based on the collisions that occur along the axes.
Generalization
The great wanderer uses all three axes for movement and makes a distinction based on the directions along those axes: up, down, left, right, forward and backward. These all represent directions along the $x,y,z$ axes in a Cartesian system but does not allow for "fluent" movement where the great wanderer would be aware of any other rotations along the horizon, other than $\frac{\pi}{2}$ rads.
Let's take for instance a 2-dimensional Cartesian system with two axes $x$ and $y$:
,.--'''''--..
,-' y ^ /`-.
,' | / `.
,' | / `.
,' up | / r+ `.
/ |-+ |
| O| | |
| - - - - - +----------> |
| left / | right x |
`. / .'
| / | /
\ / r- down /
`. / | ,'
`._ _,'
`-.__ __.-'
`''''
Up to this point in the article, we notice that the automaton is able to distinguish between "up", "down", "left", "right", "forward" and "backward", which all represent $\frac{pi}/2$ radians rotations around the axes $x$,$y$ and $z$ from origin point $O$. If we simply the model, as shown in the figure above, then we only have 4 directions along the $x,y$ axes.
We can now circumscribe the Cartesian system inside a circle with $\frac{2 * \pi}$ radians and notice that the rays $r^{+}$ and $r^{-}$ describe two directions along an arbitrary rotation around the $x$ and $y$ axes.
Thus, for all chosen rotations in $\frac{2 * \pi}$ radians of the circle we obtain 2 distinct directions: $r^{+}$ and $r^{-}$ since the rays are symmetrical. Since we have already said that the great wanderer uses an automaton with 6 states, we can generalize over the states of the automaton in order to expand it so that more directions are possible. We could reverse the situation and simplify the automaton so that it would consist of two states representing directions along "just" the $x^{+}$ and $y^{+}$ axes. In that case, we would have an automaton with two states, each corresponding to the radian-rotations around the origin point:
GW = [ d(pi/2), d(0) ]
Adding back the $x^{-}$ and $y^{-}$ directions, we get an automaton with four states:
GW = [ d(3*pi/2), d(pi), d(pi/2), d(0) ]
Going even further back and by adding the $z$ axes, we obtain another two states, forward and backward:
GW = [ fwd, bwd, d(3*pi/2), d(pi), d(pi/2), d(0) ]
We can observe that the number of angles chosen along the arc of the circle is directly linked to the number of states in the automaton.
We can thus define something called course affinity which would be the number of states that the automaton of a great wanderer would have and it will describe the number of possible directions that the wanderer could both sense (!) and move along.
Geometries
It is also clear that the geometric shape of the great wanderer is related to its course affinity. For example, for a 6-state free roamer, a number of 6 sensors is needed (each symmetrically placed at $pi$-radians) from the centre of the object in order to detect collisions.
Thus, a 6-state automaton would need 6 sensors which describe the 6 directions of the automaton. It is interesting to note that the number of states will always be even for a complete wanderer that senses a direction and its opposite.
up ^ y+
| / forward
+-|---+/ z+
/ | //
/ | //|
left +----|+/ + right
- - - -|- - +|-------->
-x | /|| / x+
| ||/
+-/--|+
| down
backward / y-
z-
Thus, we know that a 6-state automaton will require a symmetrical geometric body with 6 symmetrically placed sensors.
Suppose we additionally add the bisectrices of each plane defined by the 2-combinations of the axes $x,y,z$ minus the singularities $x,x$, $y,y$ and $z,z$. When we add the bisectrices, we are really just rotating the Cartesian system around the origin point by $\frac{\pi}{4}$ and thereby adding another 6 directions and obtaining thus 12 directions which describe a dodecahedron:
As, we said, we can generalize and observe that the number of faces is given by the rotation of the Cartesian system in $\frac{\pi}{4}$ increments, duplicating each time the number of axes and the number of directions.
For 3 axes, we have 6 directions, and hence 6 faces (cube). For 6 axes, we have 12 directions, and hence 12 faces (dodecahedron). For 12 axes, we have 24 directions, and hence 24 faces (24-cube). For $n$ axes, we have $2n$ directions (2n-cube).
Every time the number of faces being an even number (multiples of 2).
Thus an n-axes wanderer, requires 2n-state automatons with 2n faces. The general formula that maps axes to states is given by:
$$ n-axes -> 2n->directions -> 2n-faces $$
such that each axis requires 2 states, which allows the movement of a generalized great wanderer in $2n$ directions.
Geometric Convergence
We can observe that each time we rotate the Carthesian system in order to generate 2n directions, we are really just generating multiples of 2n-Hypercubes. It is interesting to note that if the even number if faces ($2n$) were replaced by an uneven $2n+1$ iterator over geometries, we would obtain only theoretical and non-practical geometries which could not be engineered.
Also, it is consequential that by increasing the number of faces of a cube, the shape will eventually converge to a sphere - similar to increasing the number of sides of a square which converges to a circle.
Automaton Expansion
Now that we have deduced the correspondence between axes, directions, faces and states, we can automatically generate code that will take as input the number of directions and create an n-great wanderer that moves along those directions.
This is primarily due to the symmetry of the code that great wanderer uses, in which every state is defined by the code-block:
state direction
{
state_entry()
{
currentState = "direction";
thrust(currentState);
// Anti-stuck.
llSetTimerEvent(2.0);
}
collision_start(integer num)
{
state compute;
}
timer()
{
llSetTimerEvent((float)FALSE);
vector velocity = llList2Vector(llGetObjectDetails(llGetKey(), [OBJECT_VELOCITY]), 0);
if(llFabs(llVecMag()) < ENGINE_SPEED/2)
state compute;
llSetTimerEvent(1.0);
}
}
Thus, by snapping together blocks of code, we can just alter the structure and add states.
The algorithm that is used in order to expand a great wanderer into an n-great wanderer is the following:
* expand the probability array and the named equivalent to n-axes or (2n-axes)-directions:
list qD = [ "forward", "backward", "left", "right", "up", "down", ..., (2n-axes)-drections ]; list QT = [ 0.15, 0.17, 0.17, 0.17, 0.17, 0.17, ..., (2n-axes)-directions, probabilities ];
where the $qD\timesQT$ is a bijective map where each element of $qD$ maps to exactly one element of $QT$. The initial spray of probabilities in $QT$ along each direction $d$ is given by $P(d)=\frac{1}{(2n-axes)}$ such that:
$$ \sum_{n=1}^{2n} P(d) = 1 $$
* handle each (2n-axes)-direction to the cumulative probability algorithm:
if(llList2String(dirs, itra) == "right") state right;
if(llList2String(dirs, itra) == "up") state up;
if(llList2String(dirs, itra) == "left") state left;
if(llList2String(dirs, itra) == "down") state down;
.
.
.
For direction in (2n-axes) - drections:
If direction is state, then:
Jump to state.
* expand the jump table in the recomputing state compute to include n-directions, similarly to the previous point:
if(nextState == "right") state right;
if(nextState == "up") state up;
if(nextState == "left") state left;
if(nextState == "down") state down;
.
.
.
For direction in (2n-axes) - drections:
Forall state in states:
If next state is state then goto state
* extend the thrust and anti-thrust symmetrically to include the (2n-axes)-directions:
thrust:
if(direction == "right") { llSetVelocity(<-ENGINE_SPEED,0,0>, TRUE); return; }
if(direction == "up") { llSetVelocity(<0,ENGINE_SPEED,0>, TRUE); return; }
if(direction == "left") { llSetVelocity(<ENGINE_SPEED,0,0>, TRUE); return; }
if(direction == "down") { llSetVelocity(<0,-ENGINE_SPEED,0>, TRUE); return; }
.
.
.
For axis in 2n-axes:
Apply forward velocity along axis.
Return.
anti-thrust:
if(direction == "right") { llSetVelocity(<ENGINE_SPEED,0,0>, TRUE); return; }
if(direction == "up") { llSetVelocity(<0,-ENGINE_SPEED,0>, TRUE); return; }
if(direction == "left") { llSetVelocity(<-ENGINE_SPEED,0,0>, TRUE); return; }
if(direction == "down") { llSetVelocity(<0,ENGINE_SPEED,0>, TRUE); return; }
.
.
.
For axes in 2n-axes:
Apply backward velocity along axis.
Return.
Generalized Great Wanderer Algorithm
- For all n-axes, 2n-directions or 2n-faces of the wanderer, do:
- Generate a bijection mapping states to probabilities so that all probabilities add up to 1: $qD$->$QT$ and \sum_{n=1}^{2n} P(2n) = 1.
- Stable-sort both QT and qD in descending order.
- Jump to the first element in qD.
- Propulse object along that direction.
- If a collision is detected, then:
- Decrement P(n) in the $QT$ probability set by a factor (increasing factor along each axis?).
- Goto 2.
Simple is beautiful. :-)
Engineering
We use collisions to detect whether an obstacle lies in front of the generalized great wonderer (GGW) but in a practical scenario that method is less than feasible depending on the physical properties of the colliding objects which may damage the great wanderer.
However, we abstract away from collisions and replace it by the notion of detection, which can be done in several ways: for example by using heat sensors with a certain sensitivity (perhaps calibrated to the design parameters) on all the faces of the GGW. Another technical problem is propulsion. In the Second Life environment, propulsion is achieved by simply requesting it from the simulator. In a practical scenario, some sort of engine is required in order to accelerate the GGW to some velocity. The question is, how could one achieve that because all the platings / faces have sensors which must detect collisions.
One way to do achieve propulsion would be to design the platings so that they contain holes, similar to a sieve which would allow particles to flow from the GGW and propulse the object in the opposite direction.
Perhaps something like this:
+---------------------------+ <---- sensor
| |
| o o o o o o o o o o o |
| |
| o o o o o o o o o o o o o |
| |
| o o o o o o o o o o o o o |
| |
| o o o o o o o o o o o o o-------
| | | l
| o o o o o o o o o o o---------
| | | |
+-----------------------|-|-+ <----- sensor
^ |-|
| sensor l
It is important that the distribution of the holes is symmetrical relative to the axes of the plating in order to make sure that there is no stray from the direction of movement. Another possible problem is that the sensors would have to be placed on the plate as well which, in case they are heat-sensors, they would be easily impressed by the heat dispersed through the sieve. One could perhaps use a photo-electric set of sensors that are calibrated to only be impressed over some threshold that exceeds the output of the engines.
One could perhaps add another layer of detection by using the surface points given by the plating and place the sensors in the vertices, with a ruleset that would only consider that an object is in the vicinity of the plating. The most trivial could be a an inclusion-condition that says that all 4 sensors have to be impressed over some threshold in order for a detection could be sensed.
This could also provide a new spray of the probability set mentioned earlier and would be great for detecting (and correcting) minor aberrations from the flight path practically adding a feedback element to the system.
We would wager that the efficiency of the GGW is surprisingly good, given that the geometric body is a reduction of a sphere which provides a great volume compared to the surface of the plates responsible for the ejection of fuel and would allow instruments to be placed inside the GGW.
Again, if possible, regardless of the instrumentation placed inside the GGW, the center of gravity should be as close as possible to the centre of the sphere in order to maintain the overall symmetry. The symmetry is implicitly responsible for the efficiency of the system since by placing the centre of gravity in the centre of the sphere, the same amount of effort will be required in order to propulse the GGW for all directions.
It is perhaps interesting to note that given a large amount of plates, when the GGW converges to a sphere, the amount of effort required per plate in order to perform a course correction is uniformly distributed.
Not only that, but less fuel could be used by performing adaptive course-corrections in order to avoid an object.
For a cube (a 6-GGW), one can only avoid an object performing sets of two movements along perpendicular axes: (up, forward), (left, backward), etc... However, by having a large automaton, the movements could be reduced by following arcs instead of rectilinear pathways. Here is an example:
y ^ Movement
| for
| 2-axes, 4 directions
-x |
- - - G-------> +---+
| x G | |
| +---+
|-y +----------->
Movement
for
y ^ 2-axes, 8 directions
b(x,y)+\ | /b(x,y)+
\ | / _
-x \ |/ /\
- - - G-------> /
/ | \ x / +---+
/ \ G | |
b(x,y)-/ |-y \b(x,-y)- +---+
The figure above shows that on a Cartesian system with 2-axes and 4 possible directions, the only way to avoid the object (except for returning back on the same path), is to perform two course corrections: once going downward and then the other to the right. In case of 2-axes and 8 possible travel directions, given by the bisectrices of the system plane, only one course correction is needed: one burst to push the object on a path that would avoid a collision with the object.
Interestingly, by increasing the automaton to span many states for different directions, you can use less fuel to prevent collisions with objects. In some way (meh), you are converting the effort that the engines have to make to a computational effort in order to process a larger automaton: you are converting physical work to computational work (given a generalized notion of energy).