{"action":"created","issue":{"url":"https://api.github.com/repos/ondras/rot.js/issues/78","labels_url":"https://api.github.com/repos/ondras/rot.js/issues/78/labels{/name}","comments_url":"https://api.github.com/repos/ondras/rot.js/issues/78/comments","events_url":"https://api.github.com/repos/ondras/rot.js/issues/78/events","html_url":"https://github.com/ondras/rot.js/issues/78","id":110584285,"number":78,"title":"Dijkstra Maps implementation","user":{"login":"hyakugei","id":136433,"avatar_url":"https://avatars.githubusercontent.com/u/136433?v=3","gravatar_id":"","url":"https://api.github.com/users/hyakugei","html_url":"https://github.com/hyakugei","followers_url":"https://api.github.com/users/hyakugei/followers","following_url":"https://api.github.com/users/hyakugei/following{/other_user}","gists_url":"https://api.github.com/users/hyakugei/gists{/gist_id}","starred_url":"https://api.github.com/users/hyakugei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hyakugei/subscriptions","organizations_url":"https://api.github.com/users/hyakugei/orgs","repos_url":"https://api.github.com/users/hyakugei/repos","events_url":"https://api.github.com/users/hyakugei/events{/privacy}","received_events_url":"https://api.github.com/users/hyakugei/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":8,"created_at":"2015-10-09T04:02:59Z","updated_at":"2015-11-03T01:00:06Z","closed_at":null,"body":"Hey all. \r\n\r\nI read about using \"[Dijkstra Maps][2]\" for AI (see below links). I decided to give it a try, and came up with this implementation: https://gist.github.com/hyakugei/ace116bd9ce72f2bf92c\r\n \r\nThe visualization stuff on the index.html demo page is similar to the images on the \"[Dijkstra Maps Visualized][1]\" page. I tried to follow the same design style as the FOV or Map bits of Rot.js (using callbacks so as to not proscribe the data storage format). I don't know if it fits into Rot.js, or is better left as a gist/project on its own, but i thought i'd ping ya'll and see what you think.\r\n\r\nComments, suggestions etc welcome. \r\n\r\nNote - hex map formatting is not currently supported. I'm not sure how easy/hard it would be to do this. \r\n\r\n[2]: http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps\r\n[1]: http://www.roguebasin.com/index.php?title=Dijkstra_Maps_Visualized\r\n\r\n\r\n<bountysource-plugin>\r\n---\r\nWant to back this issue? **[Post a bounty on it!](https://www.bountysource.com/issues/27278655-dijkstra-maps-implementation?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github)** We accept bounties via [Bountysource](https://www.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github).\r\n</bountysource-plugin>"},"comment":{"url":"https://api.github.com/repos/ondras/rot.js/issues/comments/153208126","html_url":"https://github.com/ondras/rot.js/issues/78#issuecomment-153208126","issue_url":"https://api.github.com/repos/ondras/rot.js/issues/78","id":153208126,"user":{"login":"hyakugei","id":136433,"avatar_url":"https://avatars.githubusercontent.com/u/136433?v=3","gravatar_id":"","url":"https://api.github.com/users/hyakugei","html_url":"https://github.com/hyakugei","followers_url":"https://api.github.com/users/hyakugei/followers","following_url":"https://api.github.com/users/hyakugei/following{/other_user}","gists_url":"https://api.github.com/users/hyakugei/gists{/gist_id}","starred_url":"https://api.github.com/users/hyakugei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hyakugei/subscriptions","organizations_url":"https://api.github.com/users/hyakugei/orgs","repos_url":"https://api.github.com/users/hyakugei/repos","events_url":"https://api.github.com/users/hyakugei/events{/privacy}","received_events_url":"https://api.github.com/users/hyakugei/received_events","type":"User","site_admin":false},"created_at":"2015-11-03T01:00:06Z","updated_at":"2015-11-03T01:00:06Z","body":"I'm not sure about limiting the target cost to greater then or equal to 0 because I don't  know why you would limit it that like? If it works as is, why limit the designer/programmer? \r\n\r\nI agree that the existing API would have to change quite a bit to work with this style of map, and the way I have programmed it. There may be ways to make it \"fit\" the existing API more easily, by taking a different direction in the implementation. \r\n\r\nAbout the flee map, I don't I understand what, or what part, of the code you would change, specifically. You can't just do a simple \"move to greater values when fleeing\" - the map will then push NPCs into corners. By applying the -1.2 value to all costs, and then \"re-smoothing\" the maps costs, the map's costs move smoothly towards the farthest away points, rather then the corners. You get NPCs moving towards passage ways and doors to get away. I don't see a way to do this without an initial computation of the map's costs, the negative multiplication of all the map's costs, then a \"re-smoothing\" of those costs. [On the article page](http://www.roguebasin.com/index.php?title=Dijkstra_Maps_Visualized#--_Fleeing_AI_--) , there are the 2 example flee maps which show the subtile difference between a simple \"negation\" of the costs vs. the multiplication version. Also, I'd be wary of losing polymorphism, when thinking about how the AI could work. This would most \"break\" when wanting to implement AI in the following way, making use of multiple Dijkstra maps. Each would have a different set of Targets. One for $, one for Swords, one for Health Potions, for example. You can then give each map a \"desire\" value (per NPC), sum each map's cost values (multiplied by their \"desire\") and then simply find the lowest cost neighbour.\r\n\r\nThe \"find a range\" thing works with the maps for sure. Again, this is fine if you are not using the multiple maps style of AI as described above. Otherwise, you'd take all those 3 value locations and create a new map, with each one of the '3s' set as a target. You would then use that new map as your \"3 range\" map, and if you are an NPC which really likes to use ranged weapons, you'd have a high \"desire\" value to multiply that maps values, increasing the likelihood of it influencing the final direction that NPC might choose to move. "}}