Wintermute Engine Forum
Wintermute Engine => Scripts, plugins, utilities, goodies => Topic started by: metamorphium on November 06, 2004, 10:52:58 AM
-
Hi muters.
I have a puzzle in which I have a grid 8x8 in which there are a few tiles. They can be moved according to the puzzle rules and the point is that if I choose tile start and tile destination, it has to slide around obstacles via the shortest path there (if it's of course possible).
Several of you told me, why not use built in path finding algorithm? Well I didn't found a way so maybe I spent some extra time reinventing the wheel. On the other hand I managed to hack Dijkstra's algorithm (breadth-first search) to work with wintermute and its single dimensional arrays. From my tests in 8x8 grid the worst case was 16 different paths with 10 elements, but usuallly it's much less.
For sake of speed I am using the array pathes which is devided to segments (in my case I use 64 nodes for each path), but all this is easily tweakable with the constants.
I cleaned and commented the code (from the mess Mnemonic saw ;D ) and here it is for anyone who would need something like this.
Function for calling are initsearch(); and findroute(TileX,TileY); Source is ActiveTilie.x and ActiveTilie.y;
Enjoy :)
global PuzzleArray; // The map with obstacles (0 is free, !=0 is obstacle)
var open = new Array(64); // Open set for grid (max lenght of longest path)
var pathes = new Array (1300); // All Pathes are stored here
var pathcnt = 0; // Number of pathes
var correct_path = 0; // When path found, this one is the rightful
var ActiveTilie; // Active Tile
ActiveTilie.number = 0; // Info about selected Tile
ActiveTilie.x = 0;
ActiveTilie.y = 0;
global tilies; // Definition of tilies as appears in scene_init
const GRIDX = 8; // Grid Size X
const GRIDY = 8; // Grid Size Y
const OPENSIZE = 64; // Size of OPEN array
// This is called whenever we need to use search
function initSearch()
{
correct_path = 0;
for (var a=0;a<OPENSIZE;a=a+1)
open[a] = 0;
for (a=0;a<1299;a=a+1)
pathes[a] = -1;
pathcnt = 0;
return;
}
// Function for deleting path, which is a dead end
function deletepath(pathc)
{
var startpath = pathc*OPENSIZE;
var lastpath = (pathcnt-1)*OPENSIZE;
if (pathcnt == 1)
{
// We have no more paths. There is noway to run...
pathcnt = 0;
return;
}
if (pathc == (pathcnt-1))
{
// Deleted path is the last one
pathes[startpath] = -1;
pathcnt = pathcnt - 1;
return;
}
// Move the last part in place of deleted.
while (pathes[lastpath] != -1)
{
pathes[startpath] = pathes[lastpath];
lastpath = lastpath + 1;
startpath = startpath + 1;
}
pathes[startpath] = -1;
pathcnt = pathcnt - 1;
return;
}
// Discard last node for path branching
function popnode(pth)
{
var spos = pth*OPENSIZE;
while (pathes[spos] != -1)
{
spos = spos + 1;
}
pathes[spos-1] = -1;
return;
}
// Add note on top of path stack
function addnode(pth, x, y)
{
var spos = pth*OPENSIZE;
while (pathes[spos] != -1)
{
spos = spos + 1;
}
if (spos>((pth*OPENSIZE) + OPENSIZE-1))
{
// Too long path, it would overlap to different path = dead end
deletepath(pth);
return;
}
pathes[spos] = y * GRIDY + x;
pathes[spos+1] = -1;
return;
}
// Add path to path repository
function addpath(oldpath,px,py)
{
pathcnt = pathcnt + 1;
var startpath = (oldpath*OPENSIZE);
var newpath = (pathcnt-1)*OPENSIZE;
while (pathes[startpath] != -1)
{
pathes[newpath] = pathes[startpath];
newpath = newpath + 1;
startpath = startpath + 1;
}
pathes[newpath-1] = -1;
addnode(pathcnt-1,px,py);
return;
}
// Returns last node from path
function getLastNode(pths)
{
var spos = pths*OPENSIZE;
while (pathes[spos] != -1)
{
spos = spos + 1;
}
var news = pathes[spos-1];
return news;
}
// Gets tile number from Puzzle Grid
function getTile(x,y)
{
return PuzzleArray[y*GRIDY+x];
}
// We have to check if two tiles (sx,sy) (dx,dy) are adjacent
function isAdjacent(sx,sy,dx,dy)
{
if((dx < 0) || (dx >= GRIDY))
{
return false;
}
if((dy < 0) || (dy >= GRIDY))
{
return false;
}
if(sx == dx)
{
// The squares are adjacent if the source square is above the destination square
if((sy - 1) == dy)
return true;
// Or if the source square is below the destination square
else if((sy + 1) == dy)
return true;
}
else if(sy == dy)
{
// The squares are adjacent if the source square is left of the destination square
if((sx - 1) == dx)
return true;
// Or if the source square is right of the destination square
else if((sx + 1) == dx)
return true;
}
return false; // CELL (dest_x, dest_y) IS NOT adjacent to CELL (src_x, src_y)
}
// We have to check, if tile x,y is Open and not solid
function isOpen(x,y)
{
if( PuzzleArray[y*GRIDY+x] != 0 )
return false;
if(open[y*GRIDY+x] != 0)
return false;
return true;
}
// This is the Dijkstra's guts.
function findroute(TileX, TileY)
{
initSearch();
var actpath = 0; // Actual processed path.
var opener = 0; // Indicates how many branches are from current node. If 0, delete path.
var tmp_node; // value (global value), x,y
// Create the first path
open[ActiveTilie.y*GRIDY + ActiveTilie.x] = 1;
pathcnt = 1;
addnode(actpath,ActiveTilie.x,ActiveTilie.y);
while (pathcnt > 0)
{
// Get last node from actual path
tmp_node.value = getLastNode(actpath);
tmp_node.x = tmp_node.value % GRIDY;
tmp_node.y = ToInt(tmp_node.value / GRIDY);
opener = 0; // We have no open ends yet.
for (var ox = tmp_node.x - 1; ox < tmp_node.x + 2; ox = ox + 1)
for (var oy = tmp_node.y - 1; oy < tmp_node.y + 2; oy = oy + 1)
{
if (isOpen(ox,oy) && isAdjacent(tmp_node.x,tmp_node.y,ox,oy))
{
opener = opener + 1;
if (ox == TileX && oy == TileY)
{
//Path Found
if (opener > 1) { popnode(actpath); }
addnode(actpath,ox,oy);
correct_path = actpath*OPENSIZE;
return true; // Returning correct path
}
else
{
// Let's look some more
// Set cell as visited
open[oy*GRIDY+ox] = 1;
if (opener == 1)
{
//Go down the road.
addnode(actpath,ox,oy);
}
else
{
// Add new path
addpath(actpath,ox,oy);
} // else
} // else
} // If
} // For
if (opener == 0) deletepath(actpath); // Path is a dead end
actpath = actpath + 1; // Let's walk down the next path
if (actpath>=pathcnt) actpath=0; // We have to go to first path
}
return false;
}
-
I think that when you said "pathfinding", people thought you were talking about pathfinding for the characters. ;)
-
Sure could be the cause although I tried to say that it's puzzle with tiles :)
-
Impressive scripting, I wouldn't believe it's possible ;) Thanks for sharing.
-
I think that when you said "pathfinding", people thought you were talking about pathfinding for the characters. ;)
Oops, so did I, that's why I answered exactly with these words. And to be honest - I still don't understand it completely, but the code looks impressive. ;) Checking it some other day with some more time. (Did I mention, that I found out how the word "deadline" was created ? For sure a poor programmer died of a heart attack... at least I'm afraid of this currently. :-\)
Anyway - thanks for sharing, metamorphium! 8)
-
Ah,
I made something for your better understanding.
http://www.volny.cz/kavani/puzzle.zip
I stripped the puzzle from it so it's just moving tiles, but you can see the implementation.
Just click on tile and then anywhere on grid.
Enjoy...
-
Metamorphium,
Is it easy to put my own background picture made up of the pieces and to set the puzzle/picture as mixed up initially before the player works it out?
Also is there a restiction to size of picture/blocks as long as they are within the grid?
Great design!!
-
plese reupload file . thank you
-
I am afraid I don't have it anymore. This thread is 6 years old.
-
Please tell me. How do I use this. Help me more accurately. Thank you
-
Chris, I don't think you'd ever need this. It's an implementation of Dijkstra's algorithm. Unless you exactly know what you need to achieve using Dijkstra, you'd be better off without.
More info on algorithm is here: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
-
Hello I put this script in and called the function but it says "Function 'initsearch' is referenced but not defined". Where should I put this script and how would I go about calling it so it would work? Thanks
-
Hi, I don't know much about the script, but looking at it, the function is called "initSearch" (with capital S).
-
Thanks Mnemonic, now I don't get the error but nothing happens. I put the script in an entity click, so when it says "On Look " or whatever, it calls the function.
here is my code:
#include "scripts\base.inc"
////////////////////////////////////////////////////////////////////////////////
on "LookAt"
{
actor.GoToObject(this);
initSearch();
}
////////////////////////////////////////////////////////////////////////////////
on "Take"
{
//Game.OpenDocument("http://www.dead-code.org");
}
////////////////////////////////////////////////////////////////////////////////
on "Talk"
{
actor.GoToObject(this);
actor.Talk("Blah");
}
////////////////////////////////////////////////////////////////////////////////
on "LeftClick"
{
actor.GoToObject(this);
}
method Talk(srcString,srcActor,xPosition)
{
var twin;
if (srcActor == null) twin = "talk"; // basic window with ghost
else
twin = srcActor; // NPC window
var tmpState = Game.Interactive;
Game.Interactive = false; // we save the interactivity state for later and turn it off
var dlgWin = Game.LoadWindow("interface\system\caption.window"); // load the dialogue window
var talkRobotEnt = Scene.CreateEntity(); // create the entity used for talking
var tString = Game.ExpandString(srcString); // prepare the localized string to handle formatting
var tLength = tString.Length;
var lines = ToInt(tLength / 300) + 1; // find out how many lines will we need
dlgWin.SetImage("interface/system/wme_logo.png"); // set the image
dlgWin.Y = 425;
// set the caption parameters
talkRobotEnt.SubtitlePosRelative = false;
talkRobotEnt.SubtitlesPosXCenter = false;
talkRobotEnt.SubtitlesWidth = 680;
talkRobotEnt.SubtitlesPosX = 90;
if (xPosition != null) talkRobotEnt.SubtitlesPosX = xPosition;
talkRobotEnt.SubtitlesPosY = 630 + 15* lines; // position the caption in the window based on number of lines
talkRobotEnt.SetFont("fonts\verdana.font"); // set the speech font
talkRobotEnt.SoundPanning = false; // make the sound centered
talkRobotEnt.Talk(srcString, null, "", "", 0); // say the line
Game.UnloadObject(dlgWin); // dispose of the window
Scene.DeleteEntity(talkRobotEnt); // kill the talk entity
Game.Interactive = tmpState;
}
global PuzzleArray; // The map with obstacles (0 is free, !=0 is obstacle)
var open = new Array(64); // Open set for grid (max lenght of longest path)
var pathes = new Array (1300); // All Pathes are stored here
var pathcnt = 0; // Number of pathes
var correct_path = 0; // When path found, this one is the rightful
var ActiveTilie; // Active Tile
ActiveTilie.number = 0; // Info about selected Tile
ActiveTilie.x = 0;
ActiveTilie.y = 0;
global tilies; // Definition of tilies as appears in scene_init
const GRIDX = 8; // Grid Size X
const GRIDY = 8; // Grid Size Y
const OPENSIZE = 64; // Size of OPEN array
// This is called whenever we need to use search
function initSearch()
{
correct_path = 0;
for (var a=0;a<OPENSIZE;a=a+1)
open[a] = 0;
for (a=0;a<1299;a=a+1)
pathes[a] = -1;
pathcnt = 0;
return;
}
// Function for deleting path, which is a dead end
function deletepath(pathc)
{
var startpath = pathc*OPENSIZE;
var lastpath = (pathcnt-1)*OPENSIZE;
if (pathcnt == 1)
{
// We have no more paths. There is noway to run...
pathcnt = 0;
return;
}
if (pathc == (pathcnt-1))
{
// Deleted path is the last one
pathes[startpath] = -1;
pathcnt = pathcnt - 1;
return;
}
// Move the last part in place of deleted.
while (pathes[lastpath] != -1)
{
pathes[startpath] = pathes[lastpath];
lastpath = lastpath + 1;
startpath = startpath + 1;
}
pathes[startpath] = -1;
pathcnt = pathcnt - 1;
return;
}
// Discard last node for path branching
function popnode(pth)
{
var spos = pth*OPENSIZE;
while (pathes[spos] != -1)
{
spos = spos + 1;
}
pathes[spos-1] = -1;
return;
}
// Add note on top of path stack
function addnode(pth, x, y)
{
var spos = pth*OPENSIZE;
while (pathes[spos] != -1)
{
spos = spos + 1;
}
if (spos>((pth*OPENSIZE) + OPENSIZE-1))
{
// Too long path, it would overlap to different path = dead end
deletepath(pth);
return;
}
pathes[spos] = y * GRIDY + x;
pathes[spos+1] = -1;
return;
}
// Add path to path repository
function addpath(oldpath,px,py)
{
pathcnt = pathcnt + 1;
var startpath = (oldpath*OPENSIZE);
var newpath = (pathcnt-1)*OPENSIZE;
while (pathes[startpath] != -1)
{
pathes[newpath] = pathes[startpath];
newpath = newpath + 1;
startpath = startpath + 1;
}
pathes[newpath-1] = -1;
addnode(pathcnt-1,px,py);
return;
}
// Returns last node from path
function getLastNode(pths)
{
var spos = pths*OPENSIZE;
while (pathes[spos] != -1)
{
spos = spos + 1;
}
var news = pathes[spos-1];
return news;
}
// Gets tile number from Puzzle Grid
function getTile(x,y)
{
return PuzzleArray[y*GRIDY+x];
}
// We have to check if two tiles (sx,sy) (dx,dy) are adjacent
function isAdjacent(sx,sy,dx,dy)
{
if((dx < 0) || (dx >= GRIDY))
{
return false;
}
if((dy < 0) || (dy >= GRIDY))
{
return false;
}
if(sx == dx)
{
// The squares are adjacent if the source square is above the destination square
if((sy - 1) == dy)
return true;
// Or if the source square is below the destination square
else if((sy + 1) == dy)
return true;
}
else if(sy == dy)
{
// The squares are adjacent if the source square is left of the destination square
if((sx - 1) == dx)
return true;
// Or if the source square is right of the destination square
else if((sx + 1) == dx)
return true;
}
return false; // CELL (dest_x, dest_y) IS NOT adjacent to CELL (src_x, src_y)
}
// We have to check, if tile x,y is Open and not solid
function isOpen(x,y)
{
if( PuzzleArray[y*GRIDY+x] != 0 )
return false;
if(open[y*GRIDY+x] != 0)
return false;
return true;
}
// This is the Dijkstra's guts.
function findroute(TileX, TileY)
{
initSearch();
var actpath = 0; // Actual processed path.
var opener = 0; // Indicates how many branches are from current node. If 0, delete path.
var tmp_node; // value (global value), x,y
// Create the first path
open[ActiveTilie.y*GRIDY + ActiveTilie.x] = 1;
pathcnt = 1;
addnode(actpath,ActiveTilie.x,ActiveTilie.y);
while (pathcnt > 0)
{
// Get last node from actual path
tmp_node.value = getLastNode(actpath);
tmp_node.x = tmp_node.value % GRIDY;
tmp_node.y = ToInt(tmp_node.value / GRIDY);
opener = 0; // We have no open ends yet.
for (var ox = tmp_node.x - 1; ox < tmp_node.x + 2; ox = ox + 1)
for (var oy = tmp_node.y - 1; oy < tmp_node.y + 2; oy = oy + 1)
{
if (isOpen(ox,oy) && isAdjacent(tmp_node.x,tmp_node.y,ox,oy))
{
opener = opener + 1;
if (ox == TileX && oy == TileY)
{
//Path Found
if (opener > 1) { popnode(actpath); }
addnode(actpath,ox,oy);
correct_path = actpath*OPENSIZE;
return true; // Returning correct path
}
else
{
// Let's look some more
// Set cell as visited
open[oy*GRIDY+ox] = 1;
if (opener == 1)
{
//Go down the road.
addnode(actpath,ox,oy);
}
else
{
// Add new path
addpath(actpath,ox,oy);
} // else
} // else
} // If
} // For
if (opener == 0) deletepath(actpath); // Path is a dead end
actpath = actpath + 1; // Let's walk down the next path
if (actpath>=pathcnt) actpath=0; // We have to go to first path
}
return false;
}
-
The question is, what do you expect it to do. It's quite a specific script and meta used it to implement a rather elaborate puzzle. I don't see much practical use for it, other than as a demonstration of advanced scripting.