From 70456152fafb83e661fa882fe4e7ec04a29670fd Mon Sep 17 00:00:00 2001 From: Wesley Date: Sat, 2 Dec 2017 13:47:43 +0200 Subject: [PATCH] Add lua star, example and documentation. --- .busted | 7 ++ .gitignore | 1 + README.md | 67 +++++++++++ example/lua-star-01.png | Bin 0 -> 11209 bytes example/main.lua | 107 +++++++++++++++++ src/lua-star.lua | 208 +++++++++++++++++++++++++++++++++ tests/lua-star_spec.lua | 250 ++++++++++++++++++++++++++++++++++++++++ 7 files changed, 640 insertions(+) create mode 100644 .busted create mode 100644 .gitignore create mode 100644 example/lua-star-01.png create mode 100644 example/main.lua create mode 100644 src/lua-star.lua create mode 100644 tests/lua-star_spec.lua diff --git a/.busted b/.busted new file mode 100644 index 0000000..9a81402 --- /dev/null +++ b/.busted @@ -0,0 +1,7 @@ +return { + default = { + verbose = true, + coverage = false, + ROOT = {"tests"}, + } +} diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..a813bbb --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +example/lua-star.lua diff --git a/README.md b/README.md index 0d4142a..4f22b84 100644 --- a/README.md +++ b/README.md @@ -1,2 +1,69 @@ # lua-star + Easy A* path finding for Lua + +[lua star example screenshot](example/lua-star-01.png) + +# Quick Start + +Easy to use, it will make you more attractive and you feel sensual doing so. + + local luastar = require("lua-star") + + function positionIsOpenFunc(x, y) + -- should return true if the position is open to walk + return mymap[x][y] == walkable + end + + local path = luastar:find(width, height, start, goal, positionIsOpenFunc, useCache) + +`path` will be false if no path was found, otherwise it contains a list of points that travel from `start` to `goal`: + + if path then + for _, p in ipairs(path) do + print(p.x, p.y) + end + end + +Lua star does not care how your map data is arranged, it simply asks you if the map position at `x,y` is walkable via a callback. + +`width` and `height` is your map size. + +`start` and `goal` are tables with at least the `x` and `y` keys. + + local start = { x = 1, y = 10 } + local goal = { x = 10, y = 1 } + +`positionIsOpenFunc(x, y)` is a function that should return true if the position is open to walk. + +`useCache` is optional and defaults to `false` when not given. If you have a map that does not change, caching can give a speed boost. + +If at any time you need to clear all cached paths; + + luastar:clearCached() + +# Requirements + +* [Lua 5.x](http://www.lua.org/) + +For running unit tests: + +* [Lua Rocks](https://luarocks.org/) +* busted + +These commands are for apt-based systems, please adapt to them as needed. + + sudo apt-get install luarocks + sudo luarocks install busted + +Unit testing is done with busted, the `.busted` config already defines everything, so simply run: + + busted + +# Example + +There is an [interactive example](example/main.lua) that can be run with [Love](https://love2d.org). + +# License + +See the file [LICENSE](LICENSE) diff --git a/example/lua-star-01.png b/example/lua-star-01.png new file mode 100644 index 0000000000000000000000000000000000000000..50bbed82586f93e9ab11ebdb8cdb381b2cc779b8 GIT binary patch literal 11209 zcmds-XIxWT+V-R90TGNSNKrtgh*S|oX+Z%AMLMBFR75(F-ihTPf>%Vr0juw=Wo`W6)0x_zo zD(itjC-y<0lVG~vfd9nRI!Xh7PPr+n8PEYAf4XPyK%lE2HRT5e-pR`oKHdhf*W0Ub znBfrb`3ujYuQp$Q+%WW@Awu%%*CCbDIZx8yE(zEQmQy^xJKz24!tvnhNU!c5jQN!L z=RtPI7Hj2>caT1QO%~Tp&(uc z>-;d-o=vU_4O^E%$b49E?3|zhF+}!^T6vwqZ*AjO+zdF4&WTn(d&#FJWCSU4p19!t z<@6a#B;{y4VCzIdedgnikK$G>VM(&7_jGcnDbqA#R>|RU>X2gy7 zZjDNMtOQ18WXR+N?6I*h|L~LlI)hT;Rf}*#NEEttUjfEomv}y&yt-e|7DN=3+5Z|c zE93t2@`TSq-B{_Y1Jt&evBraxnVZX|7DrDXfmMIkw}zffGU?L}W@VFj4&27<^Kg;$ zn$UBo(9lTh&AeL3##(!@v5=v#3^v{4s3~^M9N6Wo1iRBTC6PC`egIaZbTutcD;WME}g~jww%dISHqeY{X^pu}nmcA0fuV86s z7t+?=#(aSz`}5~p_yh&3mQMD}KzZMd*#1QWTUFI}8JV)fzVR5u(OntJgl@`Br!id4 zAGd-ph=v*A>sbfK42gNwVl81bHnlbjQn7I{xi*UMhhF6C-}=C`c-_O&D-XRQVBM#T zGPk{!Y%A3@)R`|{&iO;iiBGNBCe+<_dm)Oi*&-&_lQT0m-mNNvkW%a+8{E|Ub0;P? zjyM9|gT){XoHA;1HA({M8P7VbBDq__mf6Z15ytNBHbKAtE-bm~J4xM&1 zhQYO53hp{;X-iKE?1fiXALW))+V5dcp0J;q!jfL8i8f$nAVD{1=g(ZkmSf6tihr z*j`FBuSv~QRqf569Q|1-Tko7oO1us;y8;a5?Z9-rIa)u2O0^4TG6=*@?JW|w!li=T zwEOZ_I8s^Qs!Sq0tFhY+X6n2cjPPtP6ZTjf(x@Jt%EM$C>!!>OO4s9f7t{6}4hZAo zHPl9}#LWTdu00}d2Dfdvbh-`$X%fllPp52^?oNM)h}76Q77+#wOr5{!l65B|m1I0- zs)V(x$2{K|ns1+-ySH6>-^U~&!XFQ}38kOADHcCax^_6n^?sQDr131$^JoW+%-kdm zW1hyXD>y50w82VIHO@v;mGsxHEu32%_E7yAH6UME=i3au!-mOUTXVHGF-+MLo{pzK z2@B_*xQ+UhsL;jL-siQ49}?k_z4>*qhr|wFtSs2g(=fQ~)V2Qry{wSe^Z8aM8^Opz zHbq`eVP`?q!lm#&a&NvWB96JB3S)jvD_Dz_#lFSZC0e(ZO8daYaEre zAO0R}JB)4Jn73gkrg(o6MtxeEKm#YoUzqXx*QGY^-~LN+n#^QsNQ zj~wa_wj7Gs^WvhSqJBg4_s9uu=}I7*YdOZCs;a8Z^mu13?dn4QTE8gXcDFgt zeDE!ap&+|q z#dV%hhr7df1GcE2K7EQs!TU2&kpA3&{b}%#sShD^pJiQUs=k2!j7#bP1HOx;-a4K!34E^_7dhRC~r|3hs8L*b0|6PCYgQ>bF@|Eic{ z#AN4m^RI_siTznad#E4OY;C%?cZN7p5Pkg9j*LZNCH1>9YJKQ`xT&1g7^Ei>d$+z+x?1Ln%ICZhzj3&=GH|Uj z{v4P5O*P_(l)3e%PxS8{;me*Dy9}_TpZ7TT0<|khN<3pyM9*R_o9=S8pJTeRsVSCD zW=CA&GEs0|wXyYpdM(*8!7?|flh=an{n*BZijW46!>G&hGA22+z4^mTHs49szc2Is zOjn?APo7nldN=bQ`j**RoW6$NzN-1rnQw}O2|>0~WxdqO$txl((nR0F-O54c%LLdk z93CL*wjkOYCz8Zbi>$L*G?VdD#b;rrqZ#vE?w)7ngGWACdX1k~R(x4-V)8k%i$4JJh0ws3zC zGq0sSu=-kp!*5YL2r+0pz1M_9w1i!jEk?j_-m7)tBTA&ZfhH!SK8J=aqfX(SF3l{N zLSTZJnUps0RI%1391uA*H1g1;Zd=|fu3mp`t^!PmkBvoJOy4b~C@Cp+Phhto?d?18 z+3UB0pkBl9O0tgsqqyvF_Ov4j^3qX;(Dqk55i`8SRJ^-kQf_4hc|mv6Y7Pj(XO4&> ze+1UI)oZ}|U}jUBrpA5&n`EC7z}=e%&2%;zug5-@uQLH_;mmJFixt%du7G!B0%tJv zJT;5cFl2wGL~#$Ig|TP5Iwz)d{X>hz7|D?z1zRAo(4AV?8|8%T=c|yXSAE;d#P{rS z9ffXNdXC02PG*Zs18bF29}sN6I^*Xt6`*ZE#?@b0&>B0NxBg0Q&gLvWPiX&h55;Z! z6NSlqY@Xj;z;eYS~liD_YWu z`y`vOwU}>$VzE5D=I3lw!^7j`tZjZUyf=_Xie97>DA6w1lPlMT>^Nj@yUfK7r+S%L zZRt-P)YYL555!>cqO1m%=p;X5zwN-$?+`sbvb0~HrH{|DzWYVrZ9^1!!hLsxorRUP z0E00AingHG_8(<}U51{i@{i7Q;Q|E#hFp?3N7?s{Zusxxpg{l)^%h$T17XSq({~ter{`l;%_O-H&d)<41K&(mzozemJ)p z8-G@vUUKEYM@DY@MJ9HS$B+slVtVUz-Jo4C1Lc?up3FOlA97Ca2#oBd$M40@SYbAM zhMps~X$vVQ2JE_UZkV|(5npP4FrV5~3RQ~-&SvK(*s%T9gEJfRLz1sV&3VWZ`GubQ zeu`zyG+z;+LQDL;6?6GL6_RIBfBxnDJqh&&g32~m5jLm3C=c;yu)a1xbCRrWJWZ3^ zpKF;Zxmck#2x(IAM_#yNuLLKJ* z40C+T$N~T5du2^z8ZGbUczR^A2yHi{hQ1zVR^_nfDQT>qWKsi6j40(T|C!#|8zI z6UlG_pVM;0cb12F4_$E+o~^b_@$D><-N7Cq)<7nx`U~}v=`5KTN>DWeg8N}%44sL0 z+9QN5^;geHh>L$lQh{;LY{Y87oUus@H1|-Cy#umxavXLyz6};z1%V|aE57FpezZ!@ zoLpwnx`Z|unAI&xY&T$(=kAT{^}W5LW-+`X<0Fhpo!rH6jqbk#UrgkyMwHEmC+9@U zLj{i>)l1dfwLhd?kM)w#)@$l!H3i>TKB4);_-F1mE3A1d6nVEUF#53epd0eYHtuaI z3UkJe9(-oFSsPyXwA2Ga4iz{Fv#bxlln$xYuSYz!53$8#0<5bMDQ-A9@Rq;`@4*F)WP>sH_mF!!nxo+ z)oEGx*C)|AO>SVqM>>|{0c@Whg|xMG_ND6wFGW0+Y~NkHRmP|BX7)G2#};9$3oW*! z^disJmjeE2FnP*4?Z(%*8%q&SFyZ8Ibqy_jbKJe=iud|sze`qt5eP3~9tM)kBfD>Q zHM1$QOA#k^srL)2vsdoOn0g!FP|KCFp}q69ve0wV7@K*n<^2gQ>$&HP#=YV=tJ8J8 zbx_iB9>RfmS-(OIfu3-=3TdJ>?Nl<7&+=L6E|-0~8i9rsFCw%`u1tCCSd6(pjt&ob zJ@wyn)7k4vauYqb?djRwuxM+Ov9*IsxJ))gXVx8JZ)xyxmU>VO4i4L%J|nT-kwL4QehSBzX5>%t6jzzAJE(y9JzFjEq&pQD;6BQ@gJG2|6EvpAF926^QKxtLW1YBRgU;}KDCY}?NbD~ z*RR^=W_CbbJZzTS9(ge8eFs}yR?!4gZH7RFsxy{AW)r#a=pj2pHx%nU0i?%g*|$bN zCQ}NQmKXGB_Xi_-U zPvVi4m9k+VKB>=R$(HUC(6V#u+GBJK(@oReMLiFnjQ4LLvIf?v zw~K0AU~^kjmb+%*Bnho}h*w_V)_Aw%Va94rz{s)`ze?J)gg-SLs-lq5j20dmvvA;3 z+p$@@vn#X?o&dG;5C^CN@&jfSK43$Z`GNh(-2h}YW!PE?l|k4n{Nz01%4oAD$_|_ z>HAM_;J<3ZdDHdKtSnyZ=g-F?n;pzW<9Wrw3cW>UcX2%4Fd#93)PL=hcIQ<4I+O5v zZoc7k6CPvHHw1L+CnBGhBEH{=H+K#BbrKa!x?stD$j>$(iAGk9RT)m(JbPw4RA>S@ zJHR1m_%$RXMCyiJ!hQHC4QQWMXdk5G;jsiXSTDZ-EDh-6`$jN`WzJ&ii3>d!NQb-Y z&*=^P@JC8~LF3-p3X&Jjy_@34JVRG1djZsddZDU7XKM9|LnsM=u7@OYU^an+Bn1 zc<=YBFUS47VdRzX>MrZ1?-0qe^(2VO1Ze_;VE725V-ZN196!h&(lRYLEIrt4`o_IM zoPrNpv7>h6Zh#t)y3`YC=_?~8N4|AK$ht{D@PS_akCl2^X$iC-kO-`RG7S&ad;h}| zw;a)XeWJ!A+A6(?%toh}aQC?&4-fEFBq}C`_g8aim*cfN7HlmQ^a?yYO6AWx*G$re zbV|##A3efItF;5&=jG6OVSEXo_2}Y!0DU)H6VXkXmKZu&um)Fx)X&YTOmv-N?3|4+ zh7)JaAVUeX-2#9Ws&jAB2t}~2%*HS}*m8Xfh~Av;a^MbP9AJRbHW>*F76^1JV$cL0+#CgFyfa7nc8 z$QK`MX;&~S-pQON#ANTZ;N|MqTpy^tny*vP4qo7@6lZ!F_c#cQFS8xL{s|dbT<7Dr z95KVP+&E@8uh2OFrBx`CRev9@#+F$WTsg)`b6=vgF?fn?GN9`1SH@loWL-O1z*2X0 z)EkhEDn(bU-4f&2hde&^MfJzj@{f`QK#3tNkbMfx=8XPRb@yyN(esEIvfuKKiwCnuo*3-9vOO%Zd71QVRZZl`v0Ak5yB;o6 zvi(@TdG?uV`Z`6`-`fb9Z~EeP!G2tc)^Id z22PNwQL?dS959{b!QDfEcB@!0ew=#$%=a725dUnVecg=f)l0rg>m#4N-dNTx!WiFi zrey{}D*%sq7w=Kt?Ix9#?jw8||0wF$y^)8X=+d&pFjKEy10jGOD4{9hg$$7B(J9`9 zmkjTg4DShOuHTUaBM(-0F<7yv6y_0xAOd(w8Uf05f)`b(ezw*O>e zMMHiqP`GW^JR6vkF|=3Hq%X-3Mb_R{(q#WXt?bG)4V^6vZ}ZDlQ#i)XeSFE^-%GnrfmZ+y|Kvkm`^a%;?1Z@K*E!d`<)})}R!S(abU2} zVhwIeZ=Ss*gbb{Y=vF9xXvO+%`UUkK-${1B!!&^JT}l;MS!X#!h#eHQY_jKQpm7FK z8!aVMJ$HAee(s2&w@p+|NdXIf9`u|cC7t%Jd@hXwSI;YM@Xs%rU}9W4c7*fniQgM( zUxIGswqJGXoHUi5jH}ZGG-{bR(@92vXPih2@b*i&=a%8RKbyckcrD{ic*uEMAk^tV zr}<8YhKA)|fkIVC2CFwOU%b`>g#39>nQOVb54K&XHQodF$fWuKGRYDII_rM?E`W&? zzhc_7Z~$<1frJsMR2*g3T`C`y)!HJLZBr?4kVr$G<_D7sBo%oL_{1_P!L+BS{%!7}1H$;Ri8`R;81Z}2K>#QoOFSSijZcw84tMt@G`0@UyrV*uXalcuWv z9%bu)jo0bp6>-JYw!1@qYzLQe%t=Z!tbl`5Q!e0ThkpSibY8JQKn)Hg2WV)j4E|$YWlXCx*rh?b2DeNFB4uAuE{J(8IEyz&#$6EDz_d}rT)U(dZ(%L+J z5eA0|{s2E7*ay!Gt+=O7^d|lQbe{cT?hePKRn_sjZR365>k1!B09mjcG33ZSwN@G> z`Y7sHaSCWY7x`>&!TN6fL)KTSvPiXWh{`6%r;9dPKhsfMeQlgV%MpXT9`f8b-fIgI zR|PKjNy5<|A-~ArC`nzd@5T{T`Plg)*6|h6?5`i{pfU0PQu>w28b)_=N*f6sRw`P= zd%})34tJ%F%!-m~yU50!Qamni6;oavSoW9p=q|&r5{IkNQjZ8}g9!zLZa&)K-cNo9 zYORe|A%DS+`S`}J=I;8I0)eyO+i~=DWG1M4-+pjLo8Q)`OSC8f(?T|;yZ-9H413~# zM}fIMErlHVPPO~xbBPM}^_q63{QS37P=_6bZCdS3apZxDR&b8%BlTypl0JKunF zD?_^l-RRvU?dJrN`XwhQJClK+_KqHM6a;hWJ;z87SY>eBrmMC zOaAJ`vD2uUq<`%rTWKTrgdb)yb+WQ?q0= zRb>jGZov-r>{L!a;#BKCPKtZn@i?4G9b5N>_l)@Q8DCu9uy9={epO1dIkPE7+$ zSiixU?4}d7vA7Mq@M9*i#2A!zVIYY6T|sM2;oqD-naz?lw_E#`Joi~Cv7XnRXMwAq z8r8YSPB58v1dJCs3|U%vF`Oz*gJgk0pswR~@gKO`^LGXEvM14qmyhqJghW5ELo@4I zy%YfgwE()}K|l8^$gd5YuhIH$}I<25Wv_!0YpYn+!4@9zBDd-3ITgN zQ?&-QP0zRvU-?j3fvr~H95rq2;f=-U0t+LXX)}NZw?_m;3~8PQflMt@ZY%?4L%gYsidl7cmo8YGxxXznL7u%|6=;XfAEgmKdgZcjs}yxvEdF-y1!)J zu`P(7?UKzgLGI7$;oLx=mxiuK2X5V5ecj)_Rmz?PfoxB+aIVB;$@^960-KPh5|Wc0 xmq*JrqkeqIl3huDKAK1e0$~zu&=w2SBjT_c%GtGc1P}orwTD{D#fpz#{})3>TOj}d literal 0 HcmV?d00001 diff --git a/example/main.lua b/example/main.lua new file mode 100644 index 0000000..460d99c --- /dev/null +++ b/example/main.lua @@ -0,0 +1,107 @@ +--[[ + + Lua star example - Run with love (https://love2d.org/) + + Copyright 2017 wesley werner + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see http://www.gnu.org/licenses/. + +]]-- + +local luastar = require("lua-star") + +-- a 2D map where true is open and false is blocked +local map = { } +local mapsize = 10 +local screensize = 500 +local tilesize = screensize / mapsize + +-- path start and end +local path = nil +local start = { x = 1, y = 10 } +local goal = { x = 10, y = 1 } + +function love.load() + + love.window.setMode( screensize, screensize ) + + -- build an open map + for x=1, mapsize do + map[x] = {} + for y=1, mapsize do + map[x][y] = true + end + end + + requestPath() + +end + +function love.keypressed(key) + + if key == "escape" then + love.event.quit() + end + +end + +function love.draw() + + -- draw walls + love.graphics.setColor(255, 255, 255) + for x=1, mapsize do + for y=1, mapsize do + local fillstyle = "line" + if map[x][y] == false then fillstyle = "fill" end + love.graphics.rectangle(fillstyle, (x-1)*tilesize, (y-1)*tilesize, tilesize, tilesize) + end + end + + -- draw start and end + love.graphics.print("START", (start.x-1) * tilesize, (start.y-1) * tilesize) + love.graphics.print("GOAL", (goal.x-1) * tilesize, (goal.y-1) * tilesize) + + -- draw the path + if path then + for i, p in ipairs(path) do + love.graphics.setColor(0, 128, 0) + love.graphics.rectangle("fill", (p.x-1)*tilesize, (p.y-1)*tilesize, tilesize, tilesize) + love.graphics.setColor(255, 255, 255) + love.graphics.print(i, (p.x-1) * tilesize, (p.y-1) * tilesize) + end + end + +end + +function love.mousepressed( x, y, button, istouch ) + + local dx = math.floor(x / tilesize) + 1 + local dy = math.floor(y / tilesize) + 1 + map[dx][dy] = not map[dx][dy] + requestPath() + +end + +function positionIsOpenFunc(x, y) + + -- should return true if the position is open to walk + return map[x][y] + +end + +function requestPath() + + path = luastar:find(mapsize, mapsize, start, goal, positionIsOpenFunc) + +end diff --git a/src/lua-star.lua b/src/lua-star.lua new file mode 100644 index 0000000..38c512c --- /dev/null +++ b/src/lua-star.lua @@ -0,0 +1,208 @@ +--[[ + lua-star.lua + + Copyright 2017 wesley werner + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see http://www.gnu.org/licenses/. + + References: + https://en.wikipedia.org/wiki/A*_search_algorithm + https://www.redblobgames.com/pathfinding/a-star/introduction.html + https://www.raywenderlich.com/4946/introduction-to-a-pathfinding +]]-- + +--- Provides easy A* path finding. +-- @module lua-star + +local module = {} + +--- Clears all cached paths. +function module:clearCached() + module.cache = nil +end + +-- (Internal) Returns a unique key for the start and end points. +local function keyOf(start, goal) + return string.format("%d,%d>%d,%d", start.x, start.y, goal.x, goal.y) +end + +-- (Internal) Returns the cached path for start and end points. +local function getCached(start, goal) + if module.cache then + local key = keyOf(start, goal) + return module.cache[key] + end +end + +-- (Internal) Saves a path to the cache. +local function saveCached(start, goal, path) + module.cache = module.cache or { } + local key = keyOf(start, goal) + module.cache[key] = path +end + +-- (Internal) Return the distance between two points. +-- This method doesn't bother getting the square root of s, it is faster +-- and it still works for our use. +local function distance(x1, y1, x2, y2) + local dx = x1 - x2 + local dy = y1 - y2 + local s = dx * dx + dy * dy + return s +end + +-- (Internal) Clamp a value to a range. +local function clamp(x, min, max) + return x < min and min or (x > max and max or x) +end + +-- (Internal) Return the score of a node. +-- G is the cost from START to this node. +-- H is a heuristic cost, in this case the distance from this node to the goal. +-- Returns F, the sum of G and H. +local function calculateScore(previous, node, goal) + + local G = previous.score + 1 + local H = distance(node.x, node.y, goal.x, goal.y) + return G + H, G, H + +end + +-- (Internal) Returns true if the given list contains the specified item. +local function listContains(list, item) + for _, test in ipairs(list) do + if test.x == item.x and test.y == item.y then + return true + end + end + return false +end + +-- (Internal) Returns the item in the given list. +local function listItem(list, item) + for _, test in ipairs(list) do + if test.x == item.x and test.y == item.y then + return test + end + end +end + +-- (Internal) Requests adjacent map values around the given node. +local function getAdjacent(width, height, node, positionIsOpenFunc) + + local result = { } + + local positions = { + { x = 0, y = -1 }, -- top + { x = -1, y = 0 }, -- left + { x = 0, y = 1 }, -- bottom + { x = 1, y = 0 }, -- right + -- include diagonal movements + { x = -1, y = -1 }, -- top left + { x = 1, y = -1 }, -- top right + { x = -1, y = 1 }, -- bot left + { x = 1, y = 1 }, -- bot right + } + + for _, point in ipairs(positions) do + local px = clamp(node.x + point.x, 1, width) + local py = clamp(node.y + point.y, 1, height) + local value = positionIsOpenFunc( px, py ) + if value then + table.insert( result, { x = px, y = py } ) + end + end + + return result + +end + +-- Returns the path from start to goal, or false if no path exists. +function module:find(width, height, start, goal, positionIsOpenFunc, useCache) + + if useCache then + local cachedPath = getCached(start, goal) + if cachedPath then + return cachedPath + end + end + + local success = false + local open = { } + local closed = { } + + start.score = 0 + start.G = 0 + start.H = distance(start.x, start.y, goal.x, goal.y) + start.parent = { x = 0, y = 0 } + table.insert(open, start) + + while not success and #open > 0 do + + -- sort by score: high to low + table.sort(open, function(a, b) return a.score > b.score end) + + local current = table.remove(open) + + table.insert(closed, current) + + success = listContains(closed, goal) + + if not success then + + local adjacentList = getAdjacent(width, height, current, positionIsOpenFunc) + + for _, adjacent in ipairs(adjacentList) do + + if not listContains(closed, adjacent) then + + if not listContains(open, adjacent) then + + adjacent.score = calculateScore(current, adjacent, goal) + adjacent.parent = current + table.insert(open, adjacent) + + end + + end + + end + + end + + end + + if not success then + return false + end + + -- traverse the parents from the last point to get the path + local node = listItem(closed, closed[#closed]) + local path = { } + + while node do + + table.insert(path, 1, { x = node.x, y = node.y } ) + node = listItem(closed, node.parent) + + end + + saveCached(start, goal, path) + + -- reverse the closed list to get the solution + return path + +end + +return module diff --git a/tests/lua-star_spec.lua b/tests/lua-star_spec.lua new file mode 100644 index 0000000..65a8722 --- /dev/null +++ b/tests/lua-star_spec.lua @@ -0,0 +1,250 @@ +describe("Lua star", function() + + -- start is always top left (1,1) + -- goal is always bottom right (10, 10) + local start = { x = 1, y = 1 } + local goal = { x = 10, y = 10 } + local map = nil + + -- define some test maps (10 x 10) + local mapsize = 10 + local openmap = [[ + 0000000000 + 0000000000 + 0000000000 + 0000000000 + 0000000000 + 0000000000 + 0000000000 + 0000000000 + 0000000000 + 0000000000 + ]] + + local openmapSolution = { + { x = 1, y = 1 }, + { x = 2, y = 2 }, + { x = 3, y = 3 }, + { x = 4, y = 4 }, + { x = 5, y = 5 }, + { x = 6, y = 6 }, + { x = 7, y = 7 }, + { x = 8, y = 8 }, + { x = 9, y = 9 }, + { x = 10, y = 10 }, + } + + local simplemap = [[ + 0000000000 + 0000000110 + 0000001110 + 0000011100 + 0000111000 + 0001110000 + 0011100000 + 0111000000 + 0000000000 + 0000000000 + ]] + + local simplemapSolution = { + { x = 1, y = 1 }, + { x = 2, y = 2 }, + { x = 3, y = 3 }, + { x = 4, y = 4 }, + { x = 4, y = 5 }, + { x = 3, y = 6 }, + { x = 2, y = 7 }, + { x = 1, y = 8 }, + { x = 2, y = 9 }, + { x = 3, y = 10 }, + { x = 4, y = 10 }, + { x = 5, y = 10 }, + { x = 6, y = 10 }, + { x = 7, y = 10 }, + { x = 8, y = 10 }, + { x = 9, y = 10 }, + { x = 10, y = 10 }, + } + + local complexmap = [[ + 0000000000 + 1111111110 + 0000000000 + 0111111111 + 0100110000 + 0101010100 + 0001010110 + 1111011010 + 0000000010 + 0000000010 + ]] + + local complexmapSolution = { + { x = 1, y = 1 }, + { x = 2, y = 1 }, + { x = 3, y = 1 }, + { x = 4, y = 1 }, + { x = 5, y = 1 }, + { x = 6, y = 1 }, + { x = 7, y = 1 }, + { x = 8, y = 1 }, + { x = 9, y = 1 }, + { x = 10, y = 2 }, + { x = 9, y = 3 }, + { x = 8, y = 3 }, + { x = 7, y = 3 }, + { x = 6, y = 3 }, + { x = 5, y = 3 }, + { x = 4, y = 3 }, + { x = 3, y = 3 }, + { x = 2, y = 3 }, + { x = 1, y = 4 }, + { x = 1, y = 5 }, + { x = 1, y = 6 }, + { x = 2, y = 7 }, + { x = 3, y = 6 }, + { x = 4, y = 5 }, + { x = 5, y = 6 }, + { x = 5, y = 7 }, + { x = 5, y = 8 }, + { x = 6, y = 9 }, + { x = 7, y = 9 }, + { x = 8, y = 8 }, + { x = 7, y = 7 }, + { x = 7, y = 6 }, + { x = 8, y = 5 }, + { x = 9, y = 6 }, + { x = 10, y = 7 }, + { x = 10, y = 8 }, + { x = 10, y = 9 }, + { x = 10, y = 10 }, + } + + local unsolvablemap = [[ + 0000000000 + 0000000000 + 0000000000 + 0000000000 + 1111111111 + 0000000000 + 0000000000 + 0000000000 + 0000000000 + 0000000000 + ]] + + -- convert a string map into a table + local function makemap(template) + map = { } + template:gsub(".", function(c) + if c == "0" or c == "1" then + table.insert(map, c) + end + end) + end + + -- get the value at position xy on a map + local function mapTileIsOpen(x, y) + return map[ ((y-1) * 10) + x ] == "0" + end + + local function printSolution(path) + print(#path, "points") + for i, v in ipairs(path) do + print(string.format("{ x = %d, y = %d },", v.x, v.y)) + end + for h=1, mapsize do + for w=1, mapsize do + local walked = false + for _, p in ipairs(path) do + if p.x == w and p.y == h then + walked = true + end + end + if walked then + io.write(".") + else + io.write("#") + end + end + io.write("\n") + end + end + + -- begin tests + + it("find a path with no obstacles", function() + + local luastar = require("lua-star") + makemap(openmap) + local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + --printSolution(path) + assert.are.equal(10, #path) + assert.are.same(openmapSolution, path) + + end) + + it("find a path on a simple map", function() + + local luastar = require("lua-star") + makemap(simplemap) + local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + --printSolution(path) + assert.are.equal(17, #path) + assert.are.same(simplemapSolution, path) + + end) + + it("find a path on a complex map", function() + + local luastar = require("lua-star") + makemap(complexmap) + local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + --printSolution(path) + assert.are.equal(38, #path) + assert.are.same(complexmapSolution, path) + + end) + + it("find no path", function() + + local luastar = require("lua-star") + makemap(unsolvablemap) + local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + assert.is_false(path) + + end) + + it("does not cache paths by default", function() + + local luastar = require("lua-star") + makemap(openmap) + local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + local samepath = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + assert.is_not.equal(path, samepath) + + end) + + it("caches paths", function() + + local luastar = require("lua-star") + makemap(openmap) + local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true) + local samepath = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true) + assert.are.equal(path, samepath) + + end) + + it("clears cached paths", function() + + local luastar = require("lua-star") + makemap(openmap) + local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true) + luastar:clearCached() + assert.is_nil(luastar.cache) + + end) + +end) + -- 2.44.0