tests/lua-star_spec.lua

   1 describe("Lua star", function()
   2
   3     -- start is always top left (1,1)
   4     -- goal is always bottom right (10, 10)
   5     local start = { x = 1, y = 1, z = 1 }
   6     local goal = { x = 10, y = 10, z = 1 }
   7     local map = nil
   8
   9     -- define some test maps (10 x 10)
  10     local mapsize = 10
  11     local openmap = [[
  12                 0000000000
  13                 0000000000
  14                 0000000000
  15                 0000000000
  16                 0000000000
  17                 0000000000
  18                 0000000000
  19                 0000000000
  20                 0000000000
  21                 0000000000
  22                 ]]
  23
  24     local openmapSolution = {
  25         { x = 1, y = 1, z = 1 },
  26         { x = 2, y = 2, z = 1 },
  27         { x = 3, y = 3, z = 1 },
  28         { x = 4, y = 4, z = 1 },
  29         { x = 5, y = 5, z = 1 },
  30         { x = 6, y = 6, z = 1 },
  31         { x = 7, y = 7, z = 1 },
  32         { x = 8, y = 8, z = 1 },
  33         { x = 9, y = 9, z = 1 },
  34         { x = 10, y = 10, z = 1 },
  35     }
  36
  37     local simplemap = [[
  38                 0000000000
  39                 0000000110
  40                 0000001110
  41                 0000011100
  42                 0000111000
  43                 0001110000
  44                 0011100000
  45                 0111000000
  46                 0000000000
  47                 0000000000
  48                 ]]
  49
  50     local simplemapSolution = {
  51         { x = 1, y = 1, z = 1 },
  52         { x = 2, y = 2, z = 1 },
  53         { x = 3, y = 3, z = 1 },
  54         { x = 4, y = 4, z = 1 },
  55         { x = 4, y = 5, z = 1 },
  56         { x = 3, y = 6, z = 1 },
  57         { x = 2, y = 7, z = 1 },
  58         { x = 1, y = 8, z = 1 },
  59         { x = 2, y = 9, z = 1 },
  60         { x = 3, y = 10, z = 1 },
  61         { x = 4, y = 10, z = 1 },
  62         { x = 5, y = 10, z = 1 },
  63         { x = 6, y = 10, z = 1 },
  64         { x = 7, y = 10, z = 1 },
  65         { x = 8, y = 10, z = 1 },
  66         { x = 9, y = 10, z = 1 },
  67         { x = 10, y = 10, z = 1 },
  68     }
  69
  70     local simplemapDiagonalSolution = {
  71         { x = 1, y = 1, z = 1 },
  72         { x = 1, y = 2, z = 1 },
  73         { x = 1, y = 3, z = 1 },
  74         { x = 1, y = 4, z = 1 },
  75         { x = 1, y = 5, z = 1 },
  76         { x = 1, y = 6, z = 1 },
  77         { x = 1, y = 7, z = 1 },
  78         { x = 1, y = 8, z = 1 },
  79         { x = 1, y = 9, z = 1 },
  80         { x = 2, y = 9, z = 1 },
  81         { x = 3, y = 9, z = 1 },
  82         { x = 4, y = 9, z = 1 },
  83         { x = 5, y = 9, z = 1 },
  84         { x = 6, y = 9, z = 1 },
  85         { x = 7, y = 9, z = 1 },
  86         { x = 8, y = 9, z = 1 },
  87         { x = 9, y = 9, z = 1 },
  88         { x = 9, y = 10, z = 1 },
  89         { x = 10, y = 10, z = 1 },
  90     }
  91
  92     local complexmap = [[
  93                 0000000000
  94                 1111111110
  95                 0000000000
  96                 0111111111
  97                 0100110000
  98                 0101010100
  99                 0001010110
 100                 1111011010
 101                 0000000010
 102                 0000000010
 103                 ]]
 104
 105     local complexmapSolution = {
 106         { x = 1, y = 1, z = 1 },
 107         { x = 2, y = 1, z = 1 },
 108         { x = 3, y = 1, z = 1 },
 109         { x = 4, y = 1, z = 1 },
 110         { x = 5, y = 1, z = 1 },
 111         { x = 6, y = 1, z = 1 },
 112         { x = 7, y = 1, z = 1 },
 113         { x = 8, y = 1, z = 1 },
 114         { x = 9, y = 1, z = 1 },
 115         { x = 10, y = 2, z = 1 },
 116         { x = 9, y = 3, z = 1 },
 117         { x = 8, y = 3, z = 1 },
 118         { x = 7, y = 3, z = 1 },
 119         { x = 6, y = 3, z = 1 },
 120         { x = 5, y = 3, z = 1 },
 121         { x = 4, y = 3, z = 1 },
 122         { x = 3, y = 3, z = 1 },
 123         { x = 2, y = 3, z = 1 },
 124         { x = 1, y = 4, z = 1 },
 125         { x = 1, y = 5, z = 1 },
 126         { x = 1, y = 6, z = 1 },
 127         { x = 2, y = 7, z = 1 },
 128         { x = 3, y = 6, z = 1 },
 129         { x = 4, y = 5, z = 1 },
 130         { x = 5, y = 6, z = 1 },
 131         { x = 5, y = 7, z = 1 },
 132         { x = 5, y = 8, z = 1 },
 133         { x = 6, y = 9, z = 1 },
 134         { x = 7, y = 9, z = 1 },
 135         { x = 8, y = 8, z = 1 },
 136         { x = 7, y = 7, z = 1 },
 137         { x = 7, y = 6, z = 1 },
 138         { x = 8, y = 5, z = 1 },
 139         { x = 9, y = 6, z = 1 },
 140         { x = 10, y = 7, z = 1 },
 141         { x = 10, y = 8, z = 1 },
 142         { x = 10, y = 9, z = 1 },
 143         { x = 10, y = 10, z = 1 },
 144     }
 145
 146     local unsolvablemap = [[
 147                 0000000000
 148                 0000000000
 149                 0000000000
 150                 0000000000
 151                 1111111111
 152                 0000000000
 153                 0000000000
 154                 0000000000
 155                 0000000000
 156                 0000000000
 157                 ]]
 158
 159     -- convert a string map into a table
 160     local function makemap(template)
 161         map = { }
 162         template:gsub(".", function(c)
 163             if c == "0" or c == "1" then
 164                 table.insert(map, c)
 165             end
 166         end)
 167     end
 168
 169     -- get the value at position xy on a map
 170     local function mapTileIsOpen(x, y, z)
 171         return z == 1 and map[ ((y-1) * 10) + x ] == "0"
 172     end
 173
 174     local function printSolution(path)
 175         print(#path, "points")
 176         for i, v in ipairs(path) do
 177             print(string.format("{ x = %d, y = %d },", v.x, v.y))
 178         end
 179         for h=1, mapsize do
 180             for w=1, mapsize do
 181                 local walked = false
 182                 for _, p in ipairs(path) do
 183                     if p.x == w and p.y == h then
 184                         walked = true
 185                     end
 186                 end
 187                 if walked then
 188                     io.write(".")
 189                 else
 190                     io.write("#")
 191                 end
 192             end
 193             io.write("\n")
 194         end
 195     end
 196
 197     -- begin tests
 198
 199     it("find a path with no obstacles", function()
 200
 201         local luastar = require("lua-star")
 202         makemap(openmap)
 203         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen)
 204         --printSolution(path)
 205         assert.are.equal(10, #path)
 206         assert.are.same(openmapSolution, path)
 207
 208     end)
 209
 210     it("find a path on a simple map", function()
 211
 212         local luastar = require("lua-star")
 213         makemap(simplemap)
 214         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen)
 215         --printSolution(path)
 216         assert.are.equal(17, #path)
 217         assert.are.same(simplemapSolution, path)
 218
 219     end)
 220
 221     it("find a path on a simple map without diagonam movement", function ()
 222
 223         local luastar = require("lua-star")
 224         local excludeDiagonals = true
 225         makemap(simplemap)
 226         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, false, excludeDiagonals)
 227         --printSolution(path)
 228         assert.are.equal(19, #path)
 229         assert.are.same(simplemapDiagonalSolution, path)
 230
 231     end)
 232
 233     it("find a path on a complex map", function()
 234
 235         local luastar = require("lua-star")
 236         makemap(complexmap)
 237         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen)
 238         --printSolution(path)
 239         assert.are.equal(38, #path)
 240         assert.are.same(complexmapSolution, path)
 241
 242     end)
 243
 244     it("find no path", function()
 245
 246         local luastar = require("lua-star")
 247         makemap(unsolvablemap)
 248         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen)
 249         assert.is_false(path)
 250
 251     end)
 252
 253     it("find no diagonal path", function()
 254
 255         local luastar = require("lua-star")
 256         local excludeDiagonals = true
 257         makemap(unsolvablemap)
 258         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, false, excludeDiagonals)
 259         assert.is_false(path)
 260
 261     end)
 262
 263     it("find no diagonal path on a complex map", function()
 264
 265         local luastar = require("lua-star")
 266         local excludeDiagonals = true
 267         makemap(complexmap)
 268         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, false, excludeDiagonals)
 269         assert.is_false(path)
 270
 271     end)
 272
 273     it("does not cache paths by default", function()
 274
 275         local luastar = require("lua-star")
 276         makemap(openmap)
 277         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen)
 278         local samepath = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen)
 279         assert.is_not.equal(path, samepath)
 280
 281     end)
 282
 283     it("caches paths", function()
 284
 285         local luastar = require("lua-star")
 286         makemap(openmap)
 287         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, true)
 288         local samepath = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, true)
 289         assert.are.equal(path, samepath)
 290
 291     end)
 292
 293     it("clears cached paths", function()
 294
 295         local luastar = require("lua-star")
 296         makemap(openmap)
 297         local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, true)
 298         luastar:clearCached()
 299         assert.is_nil(luastar.cache)
 300
 301     end)
 302
 303 end)
 304