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 }
   6     local goal = { x = 10, y = 10 }
   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 },
  26         { x = 2, y = 2 },
  27         { x = 3, y = 3 },
  28         { x = 4, y = 4 },
  29         { x = 5, y = 5 },
  30         { x = 6, y = 6 },
  31         { x = 7, y = 7 },
  32         { x = 8, y = 8 },
  33         { x = 9, y = 9 },
  34         { x = 10, y = 10 },
  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 },
  52         { x = 2, y = 2 },
  53         { x = 3, y = 3 },
  54         { x = 4, y = 4 },
  55         { x = 4, y = 5 },
  56         { x = 3, y = 6 },
  57         { x = 2, y = 7 },
  58         { x = 1, y = 8 },
  59         { x = 2, y = 9 },
  60         { x = 3, y = 10 },
  61         { x = 4, y = 10 },
  62         { x = 5, y = 10 },
  63         { x = 6, y = 10 },
  64         { x = 7, y = 10 },
  65         { x = 8, y = 10 },
  66         { x = 9, y = 10 },
  67         { x = 10, y = 10 },
  68     }
  69
  70     local complexmap = [[
  71                 0000000000
  72                 1111111110
  73                 0000000000
  74                 0111111111
  75                 0100110000
  76                 0101010100
  77                 0001010110
  78                 1111011010
  79                 0000000010
  80                 0000000010
  81                 ]]
  82
  83     local complexmapSolution = {
  84         { x = 1, y = 1 },
  85         { x = 2, y = 1 },
  86         { x = 3, y = 1 },
  87         { x = 4, y = 1 },
  88         { x = 5, y = 1 },
  89         { x = 6, y = 1 },
  90         { x = 7, y = 1 },
  91         { x = 8, y = 1 },
  92         { x = 9, y = 1 },
  93         { x = 10, y = 2 },
  94         { x = 9, y = 3 },
  95         { x = 8, y = 3 },
  96         { x = 7, y = 3 },
  97         { x = 6, y = 3 },
  98         { x = 5, y = 3 },
  99         { x = 4, y = 3 },
 100         { x = 3, y = 3 },
 101         { x = 2, y = 3 },
 102         { x = 1, y = 4 },
 103         { x = 1, y = 5 },
 104         { x = 1, y = 6 },
 105         { x = 2, y = 7 },
 106         { x = 3, y = 6 },
 107         { x = 4, y = 5 },
 108         { x = 5, y = 6 },
 109         { x = 5, y = 7 },
 110         { x = 5, y = 8 },
 111         { x = 6, y = 9 },
 112         { x = 7, y = 9 },
 113         { x = 8, y = 8 },
 114         { x = 7, y = 7 },
 115         { x = 7, y = 6 },
 116         { x = 8, y = 5 },
 117         { x = 9, y = 6 },
 118         { x = 10, y = 7 },
 119         { x = 10, y = 8 },
 120         { x = 10, y = 9 },
 121         { x = 10, y = 10 },
 122     }
 123
 124     local unsolvablemap = [[
 125                 0000000000
 126                 0000000000
 127                 0000000000
 128                 0000000000
 129                 1111111111
 130                 0000000000
 131                 0000000000
 132                 0000000000
 133                 0000000000
 134                 0000000000
 135                 ]]
 136
 137     -- convert a string map into a table
 138     local function makemap(template)
 139         map = { }
 140         template:gsub(".", function(c)
 141             if c == "0" or c == "1" then
 142                 table.insert(map, c)
 143             end
 144         end)
 145     end
 146
 147     -- get the value at position xy on a map
 148     local function mapTileIsOpen(x, y)
 149         return map[ ((y-1) * 10) + x ] == "0"
 150     end
 151
 152     local function printSolution(path)
 153         print(#path, "points")
 154         for i, v in ipairs(path) do
 155             print(string.format("{ x = %d, y = %d },", v.x, v.y))
 156         end
 157         for h=1, mapsize do
 158             for w=1, mapsize do
 159                 local walked = false
 160                 for _, p in ipairs(path) do
 161                     if p.x == w and p.y == h then
 162                         walked = true
 163                     end
 164                 end
 165                 if walked then
 166                     io.write(".")
 167                 else
 168                     io.write("#")
 169                 end
 170             end
 171             io.write("\n")
 172         end
 173     end
 174
 175     -- begin tests
 176
 177     it("find a path with no obstacles", function()
 178
 179         local luastar = require("lua-star")
 180         makemap(openmap)
 181         local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
 182         --printSolution(path)
 183         assert.are.equal(10, #path)
 184         assert.are.same(openmapSolution, path)
 185
 186     end)
 187
 188     it("find a path on a simple map", function()
 189
 190         local luastar = require("lua-star")
 191         makemap(simplemap)
 192         local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
 193         --printSolution(path)
 194         assert.are.equal(17, #path)
 195         assert.are.same(simplemapSolution, path)
 196
 197     end)
 198
 199     it("find a path on a complex map", function()
 200
 201         local luastar = require("lua-star")
 202         makemap(complexmap)
 203         local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
 204         --printSolution(path)
 205         assert.are.equal(38, #path)
 206         assert.are.same(complexmapSolution, path)
 207
 208     end)
 209
 210     it("find no path", function()
 211
 212         local luastar = require("lua-star")
 213         makemap(unsolvablemap)
 214         local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
 215         assert.is_false(path)
 216
 217     end)
 218
 219     it("does not cache paths by default", function()
 220
 221         local luastar = require("lua-star")
 222         makemap(openmap)
 223         local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
 224         local samepath = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
 225         assert.is_not.equal(path, samepath)
 226
 227     end)
 228
 229     it("caches paths", function()
 230
 231         local luastar = require("lua-star")
 232         makemap(openmap)
 233         local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true)
 234         local samepath = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true)
 235         assert.are.equal(path, samepath)
 236
 237     end)
 238
 239     it("clears cached paths", function()
 240
 241         local luastar = require("lua-star")
 242         makemap(openmap)
 243         local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true)
 244         luastar:clearCached()
 245         assert.is_nil(luastar.cache)
 246
 247     end)
 248
 249 end)
 250