Please login or register.

Login with username, password and session length
Advanced search  

News:

IRC channel - server: waelisch.de  channel: #wme (read more)

Author Topic: Dijkstra puzzle  (Read 12672 times)

0 Members and 1 Guest are viewing this topic.

metamorphium

  • Global Moderator
  • Addicted to WME forum
  • *
  • Karma: 12
  • Offline Offline
  • Gender: Male
  • Posts: 1511
  • Vampires!
    • View Profile
    • CBE  software s.r.o.
Dijkstra puzzle
« 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 :)

Code: [Select]
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;

}
Logged
J.U.L.I.A. Enhanced Edition, Vampires!, J.U.L.I.A., J.U.L.I.A. Untold, Ghost in the Sheet

deadworm222

  • Regular poster
  • ***
  • Karma: 0
  • Offline Offline
  • Gender: Male
  • Posts: 197
  • Wintermute Army
    • View Profile
Re: Dijkstra puzzle
« Reply #1 on: November 06, 2004, 02:00:00 PM »

I think that when you said "pathfinding", people thought you were talking about pathfinding for the characters. ;)
Logged

metamorphium

  • Global Moderator
  • Addicted to WME forum
  • *
  • Karma: 12
  • Offline Offline
  • Gender: Male
  • Posts: 1511
  • Vampires!
    • View Profile
    • CBE  software s.r.o.
Re: Dijkstra puzzle
« Reply #2 on: November 06, 2004, 02:15:47 PM »

Sure could be the cause although I tried to say that it's puzzle with tiles :)

Logged
J.U.L.I.A. Enhanced Edition, Vampires!, J.U.L.I.A., J.U.L.I.A. Untold, Ghost in the Sheet

Mnemonic

  • WME developer
  • Administrator
  • Addicted to WME forum
  • *
  • Karma: 41
  • Offline Offline
  • Gender: Male
  • Posts: 5677
    • View Profile
    • Dead:Code Site
Re: Dijkstra puzzle
« Reply #3 on: November 07, 2004, 09:40:07 AM »

Impressive scripting, I wouldn't believe it's possible ;) Thanks for sharing.
Logged
Yes, I do have a twitter account
Please don't send me technical questions in private messages, use the forum. ::wave

Jerrot

  • Global Moderator
  • Addicted to WME forum
  • *
  • Karma: 0
  • Offline Offline
  • Gender: Male
  • Posts: 689
    • View Profile
Re: Dijkstra puzzle
« Reply #4 on: November 08, 2004, 11:12:37 PM »

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)
Logged
Mooh!

metamorphium

  • Global Moderator
  • Addicted to WME forum
  • *
  • Karma: 12
  • Offline Offline
  • Gender: Male
  • Posts: 1511
  • Vampires!
    • View Profile
    • CBE  software s.r.o.
Re: Dijkstra puzzle
« Reply #5 on: November 08, 2004, 11:28:34 PM »

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...

Logged
J.U.L.I.A. Enhanced Edition, Vampires!, J.U.L.I.A., J.U.L.I.A. Untold, Ghost in the Sheet

SBOVIS

  • Frequent poster
  • ****
  • Karma: 0
  • Offline Offline
  • Gender: Male
  • Posts: 404
  • FORGET REALITY SURRENDER TO YOUR DARKEST DREAMS
    • View Profile
    • LIMBO of the LOST
Re: Dijkstra puzzle
« Reply #6 on: March 26, 2007, 02:35:53 PM »

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!!

Logged
kind Regards
Steve Bovis
MAJESTIC STUDIOS

Chris

  • Lurker
  • *
  • Karma: 0
  • Offline Offline
  • Posts: 31
    • View Profile
Re: Dijkstra puzzle
« Reply #7 on: June 22, 2010, 03:20:49 PM »

plese reupload file . thank you
Logged

metamorphium

  • Global Moderator
  • Addicted to WME forum
  • *
  • Karma: 12
  • Offline Offline
  • Gender: Male
  • Posts: 1511
  • Vampires!
    • View Profile
    • CBE  software s.r.o.
Re: Dijkstra puzzle
« Reply #8 on: June 22, 2010, 03:28:49 PM »

I am afraid I don't have it anymore. This thread is 6 years old.
Logged
J.U.L.I.A. Enhanced Edition, Vampires!, J.U.L.I.A., J.U.L.I.A. Untold, Ghost in the Sheet

Chris

  • Lurker
  • *
  • Karma: 0
  • Offline Offline
  • Posts: 31
    • View Profile
Re: Dijkstra puzzle
« Reply #9 on: June 22, 2010, 07:55:58 PM »

Please tell me. How do I use this. Help me more accurately. Thank you
« Last Edit: June 22, 2010, 07:58:42 PM by Chris »
Logged

metamorphium

  • Global Moderator
  • Addicted to WME forum
  • *
  • Karma: 12
  • Offline Offline
  • Gender: Male
  • Posts: 1511
  • Vampires!
    • View Profile
    • CBE  software s.r.o.
Re: Dijkstra puzzle
« Reply #10 on: June 23, 2010, 01:25:09 PM »

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

Logged
J.U.L.I.A. Enhanced Edition, Vampires!, J.U.L.I.A., J.U.L.I.A. Untold, Ghost in the Sheet

piere

  • Supporter
  • Frequent poster
  • *
  • Karma: 4
  • Offline Offline
  • Posts: 301
  • Sorry for any bad english in my posts. Game on !
    • View Profile
Re: Dijkstra puzzle
« Reply #11 on: February 21, 2011, 11:16:19 PM »

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
Logged

Mnemonic

  • WME developer
  • Administrator
  • Addicted to WME forum
  • *
  • Karma: 41
  • Offline Offline
  • Gender: Male
  • Posts: 5677
    • View Profile
    • Dead:Code Site
Re: Dijkstra puzzle
« Reply #12 on: February 22, 2011, 08:37:56 AM »

Hi, I don't know much about the script, but looking at it, the function is called "initSearch" (with capital S).
Logged
Yes, I do have a twitter account
Please don't send me technical questions in private messages, use the forum. ::wave

piere

  • Supporter
  • Frequent poster
  • *
  • Karma: 4
  • Offline Offline
  • Posts: 301
  • Sorry for any bad english in my posts. Game on !
    • View Profile
Re: Dijkstra puzzle
« Reply #13 on: February 23, 2011, 03:01:32 AM »

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:

Code: [Select]
#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;



}


« Last Edit: February 23, 2011, 04:08:17 AM by piagent »
Logged

Mnemonic

  • WME developer
  • Administrator
  • Addicted to WME forum
  • *
  • Karma: 41
  • Offline Offline
  • Gender: Male
  • Posts: 5677
    • View Profile
    • Dead:Code Site
Re: Dijkstra puzzle
« Reply #14 on: February 23, 2011, 07:56:38 AM »

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.
Logged
Yes, I do have a twitter account
Please don't send me technical questions in private messages, use the forum. ::wave
 

Page created in 0.219 seconds with 22 queries.