tag:blogger.com,1999:blog-33613461.post6650357899506938509..comments2023-04-27T07:17:49.783-06:00Comments on 46 Dogs: A Star (A*) path/route finding Javascript codeUnknownnoreply@blogger.comBlogger17125tag:blogger.com,1999:blog-33613461.post-74637482115090900602013-01-08T08:54:56.768-07:002013-01-08T08:54:56.768-07:00Jack, I tweaked the code a little for you. You can...Jack, I tweaked the code a little for you. You can now pass another parameter into the a_star() function, a boolean that indicates whether diagonals should be allowed.The Writerhttps://www.blogger.com/profile/03427692209801338932noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-68889399308739327272013-01-08T08:50:15.904-07:002013-01-08T08:50:15.904-07:00Thank you for the very fast reply! I can't bel...Thank you for the very fast reply! I can't believe I didn't think of the answer when I looked at what you had done. Thank you!Jackhttps://www.blogger.com/profile/08372285238613553379noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-42157084265881950042013-01-08T07:24:26.123-07:002013-01-08T07:24:26.123-07:00I don't know if anyone still reads these comme...I don't know if anyone still reads these comments but how would you edit this to not use diagonal movement? I have tried myself but I cannot get it to work.<br /><br />Thanks.Jackhttps://www.blogger.com/profile/08372285238613553379noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-33507865276873688922012-01-14T03:12:29.747-07:002012-01-14T03:12:29.747-07:00Hi! I hope you don't mind, I added this to the...Hi! I hope you don't mind, I added this to the <a href="http://jsgamesoup.net/" rel="nofollow">jsGameSoup</a> library. <a href="http://jsgamesoup.net/jsdocs/symbols/AStar.html" rel="nofollow">Here is the documentation page for my modified version</a>. Thank you!Captain Science Manhttps://www.blogger.com/profile/07619840941275468895noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-54148096219653471762011-10-13T05:16:53.996-06:002011-10-13T05:16:53.996-06:00Thanks!Thanks!awlhttps://www.blogger.com/profile/11081224077556495610noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-33382760635047661282011-10-12T11:00:53.644-06:002011-10-12T11:00:53.644-06:00The most permissive license I could find was the M...The most permissive license I could find was the MIT license, so I slapped that on it. Basically, you can do whatever you want with the code, commercial or not.The Writerhttps://www.blogger.com/profile/03427692209801338932noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-5013920275648458762011-10-12T10:29:11.026-06:002011-10-12T10:29:11.026-06:00Can you clarify what kind of license your a star ...Can you clarify what kind of license your a star code would be under? I'd like to use it in a non commercial for fun but public project.awlhttps://www.blogger.com/profile/11081224077556495610noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-18479313446753846872011-05-18T01:20:38.413-06:002011-05-18T01:20:38.413-06:00Someone found a bug in my "Insert in Order&qu...Someone found a bug in my "Insert in Order" into open queue . I fixed the bug and updated the files (my heavily modified A* and the lightly optimized version).<br /><br />I hope this would helps anyone that want to use this code . The gains you get are from bit vectors are huge . I've seen a similar optimization on other JS A* implementations that use a "visited" variable. The insert in order only give a very minor gain (about 30% faster on 128X128) so it's reasonable not to use it.Moshehttps://www.blogger.com/profile/13467364293602691660noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-20495427160008205632011-05-07T01:47:24.919-06:002011-05-07T01:47:24.919-06:00I added my two optimizations to your original file...I added my two optimizations to your original file(commented replaced code) and named it:<br />http://niseg.moshela.com/for_46dog/a_star_46dog_opt.js <br /><br />I tested them on my very old version (10 out of 50) which used the original file. I used a double comb maze( this will fool A* to go through all dead ends):<br /><br />http://niseg.moshela.com/for_46dog/old_maze.html?maze=00807FFE00AA7FAA00AA7FAA00AA7FAA00AA7FAA00AA7FAA00AA7FAA00000000<br /><br />It seems to work fine .Moshehttps://www.blogger.com/profile/13467364293602691660noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-32762520231779383582011-05-06T11:11:51.423-06:002011-05-06T11:11:51.423-06:00I hope you tested my code before you took it all....I hope you tested my code before you took it all. ;) It's has tons of commented stuff . I don't think it would work now because I changed the heuristic into a wrapper....<br /><br />I'll explain about the board types anyways I changed the way it looks at neighbors to do this better:<br />- type 0 - original code excluding the vector cost per step (it's +1),<br />- type 1 - weighted A* there is another board with "weights" and an array with their values. this is similar to how Dwarf fortress does it.<br />- type 2 is a room navigation should be careful due to my use of [y][x] arrays. my room has array of dests and an x,y center point they are also aranged in a 2d array like the original code.<br /><br />- type 3 is a is a special in room navigation mode which ignore rooms that are not in the start and destination room - it's only useful when going from 1 room to it's neighbor<br /><br />The limit will limits the weights it's fairly half baked . I wanted to limit A* in my more advanced algorithms. This is how mode 3 was born .<br /><br />I might be moving to 3D soon . Your code was a great starting point.Moshehttps://www.blogger.com/profile/13467364293602691660noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-2964798837450882762011-05-06T09:23:35.075-06:002011-05-06T09:23:35.075-06:00Thank you, Moshe! I fixed that bug.Thank you, Moshe! I fixed that bug.The Writerhttps://www.blogger.com/profile/03427692209801338932noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-68736257121991434212011-05-06T06:11:55.619-06:002011-05-06T06:11:55.619-06:00I'm reusing your code in my path finding simul...I'm reusing your code in my path finding simulator (DF related) and I transformed it a lot so it support some more complex path finding scheme and benchmarking. I've found a small bug in your node object this.g = f; <br />You can see my work at http://niseg.moshela.com/test_maze.html <br /><br />I recently added optimizations including insert in order and bit vectors for open and closed queue ( O(1) check if a node is in there). This made the code run a few orders of magnitude faster. I've tested on a 128X128 version and performance improved from 13 seconds to about 15ms .Moshehttps://www.blogger.com/profile/13467364293602691660noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-84223413203901700302011-01-24T21:36:19.338-07:002011-01-24T21:36:19.338-07:00Thanks, id. I integrated your improvement.Thanks, id. I integrated your improvement.The Writerhttps://www.blogger.com/profile/03427692209801338932noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-55204767135006701402011-01-23T11:26:32.361-07:002011-01-23T11:26:32.361-07:00Thanks for this. It is nice and simple. There is...Thanks for this. It is nice and simple. There is one bug though. You are using Math.floor around Math.sqrt in the heuristic function. This causes the path to take odd diagonal routes that are not optimal. If you take that out then it is fine.<br /><br />Also you can speed it up by using this heuristic instead:<br /><br />var x = current_node.x-destination.x;<br />var y = current_node.y-destination.y;<br />return x*x+y*y;Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-33613461.post-8548114061145085722010-04-26T06:13:25.815-06:002010-04-26T06:13:25.815-06:00What about this http://webreflection.blogspot.com/...What about this http://webreflection.blogspot.com/2006/10/javascript-path-finder-with-star.html?Kalys Osmonovhttps://www.blogger.com/profile/10584811414503185452noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-62301628644769517422009-10-12T20:59:24.614-06:002009-10-12T20:59:24.614-06:00Oh, just a little iPhone-sized tank game I spend a...Oh, just a little iPhone-sized tank game I spend a few minutes every now and then coding when I'm bored.The Writerhttps://www.blogger.com/profile/03427692209801338932noreply@blogger.comtag:blogger.com,1999:blog-33613461.post-33752884369432402382009-10-12T15:12:34.788-06:002009-10-12T15:12:34.788-06:00I am kinda curious what side project might require...I am kinda curious what side project might require that :DXiraxhttps://www.blogger.com/profile/04199970390629356377noreply@blogger.com