const string MATCHBOX = "matchbox";
const string WALL = "shelfwall_";
const float MAX_NUMBER_OF_WALLS = 200;
void OnStart()
{
//AttachProp(MATCHBOX,"TT",NODE_FILE,0,0,0);
//AttachProp(MATCHBOX,"TT",NODE_FILE,NODE_SIZE,0,0);
AStarBegin(25,0,-11);
}
///////////////////////////////
//+ A* PATH FINDING
///////////////////////////////
const float NODE_SIZE = 2.0f;
const float NODE_SEP = 0.01f;
const string NODE_FILE = "sdiv" + NODE_SIZE + ".ent";
const float ASTAR_TIMESTEP = 0.2f;
void AStarBegin(float goalX, float goalY, float goalZ)
{
//Create the lists
stringListCreate("OpenList");
stringListCreate("ClosedList");
//Create start node
string startNode = CreateNode(0,0,0,0,"");
stringListAddItem("OpenList",startNode);
//Setup the goal node settings
SetLocalVarFloat("GoalX",goalX);
SetLocalVarFloat("GoalY",goalY);
SetLocalVarFloat("GoalZ",goalZ);
//Start
AddTimer("TIMER",2.0f,"AStarStep");
}
void AStarStep(string &in asTimer)
{
//Get a new node from the open list. If none, then destination unreachable.
string newNode = OpenList_LeastCostNode();
if(newNode == "")
{
AddDebugMessage("Error: Destination Unreachable",false);
return;
}
//Add this node to the closed list and remove from open list
stringListAddItem("ClosedList",newNode);
if(stringListRemoveItems("OpenList",newNode) != 1)
{
AddDebugMessage("Error: Multiple items removed from open list",false);
return;
}
//Goal Test
if(AStarGoalTest(newNode))
{
AddDebugMessage("Goal found",false);
FollowerBegin(newNode);
return;
}
//Node Properties
float nX = GetNodeProperty(newNode,"X");
float nY = GetNodeProperty(newNode,"Y");
float nZ = GetNodeProperty(newNode,"Z");
float nC = GetNodeProperty(newNode,"pCost")+1;
//Determine all the potential new nodes from this point
string[] reachable = { CreateNode(nX + NODE_SIZE + NODE_SEP,nY,nZ,nC,newNode),
CreateNode(nX - NODE_SIZE - NODE_SEP,nY,nZ,nC,newNode),
CreateNode(nX,nY,nZ + NODE_SIZE + NODE_SEP,nC,newNode),
CreateNode(nX,nY,nZ - NODE_SIZE - NODE_SEP,nC,newNode) };
//For each of the new nodes, add to open list if not already visited and not a wall:
for(uint i = 0; i<reachable.length(); i++)
{
string nextNode = reachable[i];
if(IsNodeColliding(nextNode) || IsNodeInPath(nextNode,"ClosedList") || IsNodeInPath(nextNode,"OpenList"))
DeleteNode(nextNode); //This node is not valid or optimal
else //Can assume nodes in open list are optimal as all path cost increments are 1.
OpenList_AddNewNode(nextNode); //Add/update the open list with this node
}
AddTimer("TIMER",ASTAR_TIMESTEP,"AStarStep");
}
float AStarHeuristic(float fromX, float fromY, float fromZ)
{
//StraightLine distance in squares
float DX = fromX - GetLocalVarFloat("GoalX");
float DY = fromY - GetLocalVarFloat("GoalY");
float DZ = fromZ - GetLocalVarFloat("GoalZ");
return sqrt(DX*DX + DY*DY + DZ*DZ) / (2 * NODE_SIZE);
}
bool AStarGoalTest(string node)
{
float dX = GetNodeProperty(node,"X")-GetLocalVarFloat("GoalX");
float dY = GetNodeProperty(node,"Y")-GetLocalVarFloat("GoalY");
float dZ = GetNodeProperty(node,"Z")-GetLocalVarFloat("GoalZ");
//Does this node contain the goal point?
return ( dX < NODE_SIZE && dY < NODE_SIZE && dZ < NODE_SIZE
&& dX > -NODE_SIZE && dY > -NODE_SIZE && dZ > -NODE_SIZE );
}
string OpenList_LeastCostNode()
{
string[] nodes = stringListItems("OpenList");
float leastCost = 999999.0f;
string bestNode = "";
for(uint i =0; i<nodes.length(); i++)
{
float cost = GetNodeProperty(nodes[i],"pCost") + GetNodeProperty(nodes[i],"hCost");
if(cost < leastCost)
{
bestNode = nodes[i];
leastCost = cost;
}
}
return bestNode;
}
void OpenList_AddNewNode(string node)
{
/*
//Use only if path costs are not the same for all nodes
//If node is already in open list, update old node to pick the best cost if new node is better
string[] nodes = stringListItems("OpenList");
for(uint i = 0; i<nodes.length(); i++)
{
string oldNode = nodes[i];
if(GetEntitiesCollide("node_"+oldNode,"node_"+node))
{
float pc1 = GetNodeProperty(node,"pCost");
if(pc1<GetNodeProperty(oldNode,"pCost"))
{
SetLocalVarFloat("node_"+oldNode+"pCost",pc1);
SetLocalVarString("node_"+oldNode+"parent",GetLocalVarString("node_"+node+"parent"));
AddDebugMessage(GetNodeFullName(oldNode) + " Updated",false);
}
DeleteNode(node);
}
}
*/
//Otherwise add the node
stringListAddItem("OpenList",node);
AddDebugMessage(GetNodeFullName(node) + " Added",false);
}
///////////////////////////////
//- A* PATH FINDING
///////////////////////////////
///////////////////////////////
//+ NODE
///////////////////////////////
string CreateNode(float nodeX, float nodeY, float nodeZ, float pCost, string parent)
{
int id = GetLocalVarInt("NodeID"); AddLocalVarInt("NodeID",1);
string name = "node_" + id;
SetLocalVarFloat(name + "X",nodeX);
SetLocalVarFloat(name + "Y",nodeY);
SetLocalVarFloat(name + "Z",nodeZ);
SetLocalVarFloat(name + "pCost",pCost);
SetLocalVarFloat(name + "hCost",AStarHeuristic(nodeX,nodeY,nodeZ));
SetLocalVarString(name + "parent",parent);
AttachProp(MATCHBOX,name,NODE_FILE,nodeX,nodeY,nodeZ);
return ""+id;
}
void DeleteNode(string node) { RemoveAttachedPropFromProp(MATCHBOX,"node_" + node); }
bool IsNodeInPath(string newNode, string path)
{
string[] nodes = stringListItems(path);
string node = "node_" + newNode;
for(uint i = 0; i<nodes.length(); i++)
if(GetEntitiesCollide(node,"node_"+nodes[i])) return true;
return false;
}
bool IsNodeColliding(string node)
{
for(int i =1; i<MAX_NUMBER_OF_WALLS; i++)
if(GetEntitiesCollide(WALL+i,"node_"+node)) return true;
return false;
}
float GetNodeProperty(string node, string property) { return GetLocalVarFloat("node_" + node + property); }
string GetNodeFullName(string node)
{
return "Node("+ GetNodeProperty(node,"X")+","+
GetNodeProperty(node,"Y")+","+
GetNodeProperty(node,"Z")+","+node+")";
}
void ClearNodeAttachments()
{
for(int i =0; i<GetLocalVarInt("NodeID"); i++)
{
if(GetEntityExists("node_"+i))
RemoveAttachedPropFromProp(MATCHBOX,"node_"+i);
}
}
///////////////////////////////
//- NODE
///////////////////////////////
///////////////////////////////
//+ PATH FOLLOWING
///////////////////////////////
const float FOLLOWER_TIMESTEP = 1.0f;
const float FOLLOWER_IMPULSE_MUL = 2.25f;
void FollowerBegin(string goalNode)
{
//Don't need the old open/closed list anymore, or the attachments.
stringListClear("OpenList");
stringListClear("ClosedList");
ClearNodeAttachments();
//Use the open list as temp storage for the route from goal->start
string parent = GetLocalVarString("node_"+goalNode+"parent");
while(parent!="")
{
stringListAddItem("OpenList",parent);
parent = GetLocalVarString("node_"+parent+"parent");
}
//Start the follower timer
SetLocalVarFloat("OldX",0);
SetLocalVarFloat("OldY",0);
SetLocalVarFloat("OldZ",0);
AddTimer("Follower",FOLLOWER_TIMESTEP,"tmrFollower");
}
void tmrFollower(string &in asTimer)
{
//Get the current node & remove from path
string[] toVisit = stringListItems("OpenList");
if(toVisit.length() == 0)
{
AddDebugMessage("At Goal",false);
return;
}
string node = toVisit[toVisit.length()-1];
stringListRemoveItems("OpenList",node);
//Work out which direction to move in
float nX = GetNodeProperty(node,"X");
float nY = GetNodeProperty(node,"Y");
float nZ = GetNodeProperty(node,"Z");
float dX = (nX - GetLocalVarFloat("OldX")) * FOLLOWER_IMPULSE_MUL;
float dY = (nY - GetLocalVarFloat("OldY")) * FOLLOWER_IMPULSE_MUL;
float dZ = (nZ - GetLocalVarFloat("OldZ")) * FOLLOWER_IMPULSE_MUL;
SetLocalVarFloat("OldX",nX);
SetLocalVarFloat("OldY",nY);
SetLocalVarFloat("OldZ",nZ);
//Move
AddPropImpulse(MATCHBOX,dX,dY,dZ,"world");
//Repeat the path follower
AddTimer(asTimer,FOLLOWER_TIMESTEP,"tmrFollower");
}
///////////////////////////////
//- PATH FOLLOWING
///////////////////////////////
///////////////////////////////
//+ MISC METHODS
///////////////////////////////
//Fixed variant of AddAttachedPropToProp
void AttachProp(string &in asPName,string &in asAName, string &in aFile, float afX, float afY, float afZ)
{
AddAttachedPropToProp(asPName,asAName,aFile,afX,afY,0,afZ,90.0f,afZ);
}
//SQRT
bool approx(float &in x, float &in y, float &in epsilon)
{ float delta = x-y; return ((delta>0?delta:-delta) <= (epsilon>0?epsilon:-epsilon)); }
const uint32 _SQRTITERATIONS=16; //Maximum number of iterations for sqrt computation
const float _SQRTDELTA=0.00001f; //Margin of error allowable if complete before iteration ceiling
float sqrt(float &in x) {
if(x<=0) return 0; //Early out - not valid input.
uint32 i = 0; float o = x * 0.5f;
while( i<_SQRTITERATIONS && !approx(o*o,x,_SQRTDELTA) && o != 0)
{ o = 0.5f * (o + x/o); i++; }
return o; }
///////////////////////////////
//- FIXED METHODS
///////////////////////////////
///////////////////////////////
//Begin String Parsing
///////////////////////////////
//+ Private Parsing functions
int _ParseDigit(uint8 digit) {
int d = digit-48; //48 is ASCII code for 0
return ((d >= 0)&&(d<=9)) ? d : -1; }
bool _ParseExp(uint8 digit) {
return (digit == 69) || (digit == 101); //ASCII for e or E
}
bool _ParseSign(uint8 digit) {
return (digit == 45); // -sign
}
bool _ParsePoint(uint8 digit) {
return (digit == 46);
}
bool _ParseExpSpace(uint8 digit) {
return (digit == 43)||(digit == 32);
}
float _ParseMakeFloat(int n1, int n2, int n3, bool hasD, bool hasE, bool signE, bool signN, int leading) {
float output = n1;
if(hasD) {
int ln=(""+n2).length() + leading; float temp=n2;
for(int i=0; i<ln; i++) temp /= 10;
output += signN?-temp:temp;
} if(hasE) {
for(int i =0; i<n3; i++)
output = signE?(output/10):(output*10);
} return output;
}
int _ParseMakeInt(int n1, int n3, bool hasE, bool signE) {
int output = n1;
if(hasE) {
for(int i =0; i<n3; i++)
output = signE?(output/10):(output*10);
} return output;
}
//-
//Parses a given string to an array of floats
float[] parseStringToFloatArray(string &in asString) {
float[] output={}; int state = 0;
bool finalise = false; //Need to store number in array?
bool reading = false; //In the process of reading a number?
bool numsign = false; //Whether or not number is signed
bool expsign = false; // " " " " " " " exponent is signed
bool hasexp = false; //Has an exponent?
bool hasdec = false; //Has points?
int numbers = 0; //Temp store for numbers
int points =0; //Temp store for decimals
int expons =0; //Temp store for exponent
int leading =0; //Temp for leading 0s on decimals
for(uint i=0; i<asString.length(); i++) { uint8 chr = asString[i];
int d = _ParseDigit(chr);
switch(state) {
case 0: { //Looking for: - or digit
if(d>=0 && d<=9) {
numbers=numsign?-d:d;
reading = true; //State we are reading a number
state = 1; //Number has begun, jump to number reading stage
} else if(_ParseSign(chr)) {
numsign=true; //Read a minus sign. Mark number as possibly signed?
} else {
numsign=false; //Didn't read a sign - reset sign state.
} break;
}
case 1: { //Read digits until a "." or exponent is found
if(d>=0 && d<=9) {
numbers=(numbers * 10) + d; //Add each digit
} else if(_ParsePoint(chr)) {
state = 2; //Read a decimal point - jump to decimal reading state
} else if(_ParseExp(chr)) {
state = 3; //Read an exponent marker - jump to exponent reading state
} else { //Nothing matches. Finish.
reading = false; finalise = true;
} break;
}
case 2: { //Read digits until an exponent is found
if(d>=0 && d<=9) {
if(d == 0 && points == 0) leading++;
points = (points * 10) + d;
hasdec=true;
} else if(_ParseExp(chr)) {
state = 3;
} else { //Nothing matches. Finish.
reading = false; finalise = true;
} break;
}
case 3: { //Looking for: - + or whitespace signs or a digit
if(d>=0 && d<=9) {
expons=d; hasexp=true; state =4;
} else if(_ParseSign(chr)) {
expsign=true;
} else if(_ParseExpSpace(chr)) {
expsign=false;
} else {
expsign=false; reading = false; finalise = true;
} break;
}
case 4: { //Reading digits for exponent
if(d>=0 && d<=9) {
expons = (expons * 10) + d; hasexp=true;
} else {
reading = false; finalise = true;
} break;
}
}
if(finalise) {
int index = output.length(); output.resize(index+1); //Resize array, store target index
output[index] = _ParseMakeFloat(numbers, points, expons, hasdec, hasexp, expsign, numsign, leading); //Store number
numbers = 0; points = 0; expons = 0; state = 0; leading=0; //Reset vars
finalise = false; reading = false; hasexp=false; expsign=false; numsign = false; hasdec=false;
}
}
if(reading) {
int index = output.length(); output.resize(index+1);
output[index] = _ParseMakeFloat(numbers, points, expons, hasdec, hasexp, expsign, numsign, leading);
}
return output;
}
//Parses a given string to an array of ints
int[] parseStringToIntArray(string &in asString) {
int[] output={}; int state = 0;
bool finalise = false; //Need to store number in array?
bool reading = false; //In the process of reading a number?
bool numsign = false; //Whether or not number is signed
bool expsign = false; // " " " " " " " exponent is signed
bool hasexp = false; //Has an exponent?
int numbers = 0; //Temp store for numbers
int expons =0; //Temp store for exponent
for(uint i=0; i<asString.length(); i++) { uint8 chr = asString[i];
int d = _ParseDigit(chr);
switch(state) {
case 0: { //Looking for: - or digit
if(d>=0 && d<=9) {
numbers=numsign?-d:d;
reading = true; //State we are reading a number
state = 1; //Number has begun, jump to number reading stage
} else if(_ParseSign(chr)) {
numsign=true; //Read a minus sign. Mark number as possibly signed?
} else {
numsign=false; //Didn't read a sign - reset sign state.
} break;
}
case 1: { //Read digits until exponent is found
if(d>=0 && d<=9) {
numbers=(numbers * 10) + d; //Add each digit
} else if(_ParseExp(chr)) {
state = 3; //Read an exponent marker - jump to exponent reading state
} else { //Nothing matches. Finish.
reading = false;
finalise = true;
} break;
}
case 3: { //Looking for: - + or whitespace signs or a digit
if(d>=0 && d<=9) {
expons=d; hasexp=true; state =4;
} else if(_ParseSign(chr)) {
expsign=true;
} else if(_ParseExpSpace(chr)) {
expsign=false;
} else {
expsign=false; reading = false; finalise = true;
} break;
}
case 4: { //Reading digits for exponent
if(d>=0 && d<=9)
{
expons = (expons * 10) + d; hasexp=true;
} else {
reading = false; finalise = true;
}
}
}
if(finalise) {
int index = output.length(); output.resize(index+1);
output[index] = _ParseMakeInt(numbers, expons, hasexp, expsign);
numbers = 0; expons = 0; state = 0; finalise = false; reading = false;
hasexp=false; expsign=false; numsign = false;
}
}
if(reading) {
int index = output.length(); output.resize(index+1);
output[index] = _ParseMakeInt(numbers, expons, hasexp, expsign);
}
return output;
}
//Parses all the digits out of a given string, ignorning sign
uint parseStringUInt(string &in asString) {
uint output = 0;
for(uint i=0; i<asString.length(); i++) {
int digit = _ParseDigit(asString[i]);
output = (digit > -1)?(10*output+digit):(output); }
return output;
}
///////////////////////////////
//End
///////////////////////////////
///////////////////////////////
//Begin String List
///////////////////////////////
//+ Constants
//Change the delimiter to suit, it is currently the null character.
const string _STRLPFX = "_!strli!_"; //Prefixed to all stringList var names
const string _STRLDLM = "\0"; //SINGLE CHARACTER Delimiter for items
//-
//+ List Management
bool stringListCreate(string &in asName) {
string name = _STRLPFX + asName;
//If Exists alread, don't overwrite
if(GetLocalVarInt(name + "_exist")==1) return false;
//Else continue as normal
SetLocalVarInt(name + "_exist",1); //State list exists
SetLocalVarInt(name + "_count",0); //Put a count on the list
SetLocalVarString(name,""); //Define list w/ empty string
return true;
}
bool stringListDestroy(string &in asName) {
string name = _STRLPFX + asName;
//If it doesn't exist - we can't destroy it
if(GetLocalVarInt(name + "_exist")!=1) return false;
//Else reduce all vars to min size - mark as not existing
SetLocalVarInt(name + "_exist",0); //State list doesn't exist
SetLocalVarInt(name + "_count",0); //Change the list count
SetLocalVarString(name,""); //Define list w/ empty string
return true;
}
bool stringListExists(string &in asName) {
return (GetLocalVarInt(_STRLPFX + asName + "_exist") == 1);
}
int stringListSize(string &in asName) {
return (GetLocalVarInt(_STRLPFX + asName + "_count"));
}
void stringListClear(string &in asName) {
string name = _STRLPFX + asName;
//Don't do anything if list doesn't exist
if(GetLocalVarInt(name + "_exist")!=1) return;
//Else reset list to defaults
SetLocalVarInt(name + "_count",0); //Put a count on the list to 0
SetLocalVarString(name,""); //Define list w/ empty string
}
//- List Management
//+ Item Management
string[] stringListItems(string &in asName) {
string str = GetLocalVarString(_STRLPFX + asName);
//Output array vars
string[] output = {};
int outputIndex = 0;
//Early-out if string is faulty
if(!StringContains(str,_STRLDLM)) return output;
//String matching vars
uint8 dlm = _STRLDLM[0];
int last = 0;
//Loop and add each substring
for(uint i =0; i<str.length(); i++) //For each char
{
if(str[i] == dlm) //If char matches delimiter
{
int len = int(i) - last; //Determine length of token to read
if(len >= 0)
{
output.resize(outputIndex+1); //Increase array size
output[outputIndex] = StringSub(str,last,len); //Get token into array
outputIndex++; //Location of next token
}
last = i+1; //Say token begins at the next char
}
}
//Return array of substrings
return output;
}
int stringListAddItem(string &in asName, string &in asItem) {
string name = _STRLPFX + asName;
//Return error value if list doesn't exist
if(GetLocalVarInt(name + "_exist")!=1) return -1;
//Add the item with the delimiter, increment count
int index = GetLocalVarInt(name + "_count");
AddLocalVarInt(name + "_count",1);
AddLocalVarString(name,asItem + _STRLDLM);
return index;
}
void stringListAddItems(string &in asName, string[] asItem) {
//Doesnt exist / Bad parameter? return.
string name = _STRLPFX + asName;
if(GetLocalVarInt(name + "_exist")!=1 || asItem.length()==0) return;
//Append all items together w/ the delimiter
string item = "";
for(uint i =0; i<asItem.length(); i++) item += asItem[i] + _STRLDLM;
//Add this new item string, Increment count
AddLocalVarString(name,item);
AddLocalVarInt(name + "_count",asItem.length());
}
string stringListGetItem(string &in asName, int alIndex) {
//This is just an array fetch + grab at index
string name = _STRLPFX + asName;
string output = "";
if(alIndex >= 0 && GetLocalVarInt(name + "_exist") == 1) //Parameters valid enough to progress?
{
string[] names = stringListItems(asName); //Get list of items
if(alIndex < int(names.length()))
{
output = names[alIndex]; //Index in bounds: set ouput to item
}
}
return output;
}
int stringListGetLastIndexof(string &in asName, string &in asItem) {
//This is a linear search of the list of items
string name = _STRLPFX + asName;
int index = -1;
if(GetLocalVarInt(name + "_exist") == 1)
{
string[] items = stringListItems(asName); //Get list of items
for(int i=0; i<int(items.length()); i++)
{ if(asItem == items[i]) index = i; } //Search for match. If match set index to index of match.
}
return index;
}
int stringListGetFirstIndexof(string &in asName, string &in asItem) {
//This is a linear search of the list of items
string name = _STRLPFX + asName;
int index = -1;
if(GetLocalVarInt(name + "_exist") == 1)
{
string[] items = stringListItems(asName); //Get list of items
for(uint i=0; i<items.length(); i++)
{
if(asItem == items[i])
{
index = int(i);
i = items.length();
}
}
}
return index;
}
bool stringListContains(string &in asName, string &in asItem) {
return stringListGetLastIndexof(asName, asItem)>=0;
}
bool stringListRemoveItemAt(string &in asName, uint alIndex) {
string name = _STRLPFX + asName;
//List exists?
if(GetLocalVarInt(name + "_exist")!=1) return false;
//Get list
string[] list = stringListItems(asName);
//Re-add all but deleted item
string item = "";
int count = 0;
bool op = false;
for(uint i =0; i<list.length(); i++)
{
if(i != alIndex)
{
item += list[i] + _STRLDLM;
count++;
}
else op=true;
}
//Set back to the array
SetLocalVarInt(name + "_count",count); //Change count
SetLocalVarString(name,item); //Redefine list
//Return if anything was deleted
return op;
}
int stringListRemoveItems(string &in asName, string asItem) {
string name = _STRLPFX + asName;
//List exists?
if(GetLocalVarInt(name + "_exist")!=1) return 0;
//Get list
string[] list = stringListItems(asName);
//Re-add all but deleted items
string item = "";
int count = 0;
int delamt = 0;
for(uint i =0; i<list.length(); i++)
{
if(asItem != list[i])
{
item += list[i] + _STRLDLM;
count++;
}
else delamt++;
}
//Set back to the array
SetLocalVarInt(name + "_count",count); //Change count
SetLocalVarString(name,item); //Redefine list
//Return if anything was deleted
return delamt;
}
//- Item Management
///////////////////////////////
//End String List
///////////////////////////////