﻿ Dijkstra puzzle
• September 22, 2018, 05:35:10 PM
• Welcome, Guest

### News:

This forum provides RSS feed. To query recent posts use this url. More...

Pages: [1]

### AuthorTopic: Dijkstra puzzle  (Read 12546 times)

0 Members and 1 Guest are viewing this topic.

#### metamorphium

• Global Moderator
• Karma: 12
• Offline
• Gender:
• Posts: 1511
• Vampires!
##### 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  ) 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 herevar pathcnt = 0; // Number of pathes var correct_path = 0; // When path found, this one is the rightfulvar ActiveTilie;                // Active TileActiveTilie.number = 0; // Info about selected TileActiveTilie.x = 0;                                        ActiveTilie.y = 0;global tilies; // Definition of tilies as appears in scene_initconst GRIDX = 8;                 // Grid Size Xconst        GRIDY = 8; // Grid Size Yconst OPENSIZE = 64; // Size of OPEN array// This is called whenever we need to use searchfunction 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 endfunction 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 branchingfunction popnode(pth){ var spos = pth*OPENSIZE; while (pathes[spos] != -1) { spos = spos + 1; } pathes[spos-1] = -1; return;}// Add note on top of path stackfunction 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 repositoryfunction 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 pathfunction 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 Gridfunction getTile(x,y){ return PuzzleArray[y*GRIDY+x];}// We have to check if two tiles (sx,sy) (dx,dy) are adjacentfunction 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 solidfunction 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

• Regular poster
• Karma: 0
• Offline
• Gender:
• Posts: 197
• Wintermute Army
##### 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
• Karma: 12
• Offline
• Gender:
• Posts: 1511
• Vampires!
##### 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
• Karma: 41
• Offline
• Gender:
• Posts: 5676
##### 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.

#### Jerrot

• Global Moderator
• Karma: 0
• Offline
• Gender:
• Posts: 688
##### 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!
Logged
Mooh!

#### metamorphium

• Global Moderator
• Karma: 12
• Offline
• Gender:
• Posts: 1511
• Vampires!
##### Re: Dijkstra puzzle
« Reply #5 on: November 08, 2004, 11:28:34 PM »

Ah,

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
• Gender:
• Posts: 404
• FORGET REALITY SURRENDER TO YOUR DARKEST DREAMS
##### 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
• Posts: 31
##### Re: Dijkstra puzzle
« Reply #7 on: June 22, 2010, 03:20:49 PM »

plese reupload file . thank you
Logged

#### metamorphium

• Global Moderator
• Karma: 12
• Offline
• Gender:
• Posts: 1511
• Vampires!
##### 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
• Posts: 31
##### 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
• Karma: 12
• Offline
• Gender:
• Posts: 1511
• Vampires!
##### 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.

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
• Posts: 301
• Sorry for any bad english in my posts. Game on !
##### 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
• Karma: 41
• Offline
• Gender:
• Posts: 5676
##### 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.

#### piere

• Supporter
• Frequent poster
• Karma: 4
• Offline
• Posts: 301
• Sorry for any bad english in my posts. Game on !
##### 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 herevar pathcnt = 0; // Number of pathes var correct_path = 0; // When path found, this one is the rightfulvar ActiveTilie;               // Active TileActiveTilie.number = 0; // Info about selected TileActiveTilie.x = 0;                                        ActiveTilie.y = 0;global tilies; // Definition of tilies as appears in scene_initconst GRIDX = 8;                // Grid Size Xconst        GRIDY = 8; // Grid Size Yconst OPENSIZE = 64; // Size of OPEN array// This is called whenever we need to use searchfunction 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 endfunction 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 branchingfunction popnode(pth){ var spos = pth*OPENSIZE; while (pathes[spos] != -1) { spos = spos + 1; } pathes[spos-1] = -1; return;}// Add note on top of path stackfunction 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 repositoryfunction 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 pathfunction 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 Gridfunction getTile(x,y){ return PuzzleArray[y*GRIDY+x];}// We have to check if two tiles (sx,sy) (dx,dy) are adjacentfunction 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 solidfunction 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
• Karma: 41
• Offline
• Gender:
• Posts: 5676
##### 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.
Pages: [1]

Page created in 0.281 seconds with 22 queries.