Botre Posted March 12, 2015 Share Posted March 12, 2015 Anyone wants to share their implementation with me ? (shameless) Or point me to a tutorial, or just write down the basic steps for me? Thanks Quote Link to comment Share on other sites More sharing options...
VladBots Posted March 12, 2015 Share Posted March 12, 2015 essentially you just need to build everything into a weighted digraph Quote Link to comment Share on other sites More sharing options...
Mysteryy Posted March 12, 2015 Share Posted March 12, 2015 Anyone wants to share their implementation with me ? (shameless) Or point me to a tutorial, or just write down the basic steps for me? Thanks Think of it as you need to overlay an edge weighted graph on to runescape. How you do that is up to you. I have made a couple of tools to autogenerate the graph, and manually generate the graph as well. Personally, mine is at least 95% autogenerated, then I go back and add manual nodes as needed. So first make an edge weighted graph and make a tool to build one using runescape variables (x, y, z, etc.). Once you make a graph (just make a small one at first), then you should make a pathfinder to be used on your graph. A* is obviously the widely used one in games. You then need to apply A* to the graph you coded/built and find a path from point A to B. Last you need to create a walker that can traverse the path you feed it using your pathfinder, handling obstacles, cross plane traversal, dungeons, etc. The way you store everything is up to you, but always keep efficiency in mind. All I have to say is good luck. :p 3 Quote Link to comment Share on other sites More sharing options...
DragonAlpha Posted March 12, 2015 Share Posted March 12, 2015 Think of it as you need to overlay an edge weighted graph on to runescape. How you do that is up to you. I have made a couple of tools to autogenerate the graph, and manually generate the graph as well. Personally, mine is at least 95% autogenerated, then I go back and add manual nodes as needed. So first make an edge weighted graph and make a tool to build one using runescape variables (x, y, z, etc.). Once you make a graph (just make a small one at first), then you should make a pathfinder to be used on your graph. A* is obviously the widely used one in games. You then need to apply A* to the graph you coded/built and find a path from point A to B. Last you need to create a walker that can traverse the path you feed it using your pathfinder, handling obstacles, cross plane traversal, dungeons, etc. The way you store everything is up to you, but always keep efficiency in mind. V All I have to say is good luck. :p Very good explanation. Had no idea on where to even start with a web walker. Was even considering doing GLOBAL a* (i know, inefficient). Thanks for the pointers. Quote Link to comment Share on other sites More sharing options...
Botre Posted March 12, 2015 Author Share Posted March 12, 2015 Think of it as you need to overlay an edge weighted graph on to runescape. How you do that is up to you. I have made a couple of tools to autogenerate the graph, and manually generate the graph as well. Personally, mine is at least 95% autogenerated, then I go back and add manual nodes as needed. So first make an edge weighted graph and make a tool to build one using runescape variables (x, y, z, etc.). Once you make a graph (just make a small one at first), then you should make a pathfinder to be used on your graph. A* is obviously the widely used one in games. You then need to apply A* to the graph you coded/built and find a path from point A to B. Last you need to create a walker that can traverse the path you feed it using your pathfinder, handling obstacles, cross plane traversal, dungeons, etc. The way you store everything is up to you, but always keep efficiency in mind. All I have to say is good luck. A couple of questions: - What exactly is the role of the node in this scenario? Is it one walkable position of an area you feed to the pathfinder? Or do you feed all walkable positions to the pathfinder (this seems expensive though)? - To generate the graph, do you walk the surface and collect map data or do you just use a cache from the map and load all data at once? - Could you explain the word "web" ? What exactly is interlinked? The nodes? If so, why would you need a pathfinder if a relation is pre-established? I have a couple more, if you don't mind, but perhaps the answers to the one above will also answer those :p Quote Link to comment Share on other sites More sharing options...
Joseph Posted March 12, 2015 Share Posted March 12, 2015 Anyone wants to share their implementation with me ? (shameless) Or point me to a tutorial, or just write down the basic steps for me? Thanks here is someone open source walker. Dont take credit for his shit please lol https://github.com/Lem0ns/Walker/tree/master/webwalk/obstacles (once your done give me your source :P) 1 Quote Link to comment Share on other sites More sharing options...
Mysteryy Posted March 12, 2015 Share Posted March 12, 2015 A couple of questions: - What exactly is the role of the node in this scenario? Is it one walkable position of an area you feed to the pathfinder? Or do you feed all walkable positions to the pathfinder (this seems expensive though)? A node is a single position in the graph. A* can be designed to handle non walkable positions, but for this case its just a waste. Only add walkable positions to your graph, it will save time in pathfinding and save memory on the graph. You feed the whole graph to A*, but that doesnt mean its inefficient. The pathfinder will only examine those positions that it thinks will get it from A to B, the rest are ignored. - To generate the graph, do you walk the surface and collect map data or do you just use a cache from the map and load all data at once? You could do it either way. I walk around and use loaded regions because I never have enough time to get more into it than that. - Could you explain the word "web" ? What exactly is interlinked? The nodes? If so, why would you need a pathfinder if a relation is pre-established? Any single position can be connected to any other position in the graph. If you imagine a grid of tiles, there is no predefined connections. A tile should only be connected to a neighboring tile which can be reached from that tile. So in runescape, i usually connect a few tiles (4) to every other tile. So for example, from tile A I can reach neighboring tiles B, C, D, but E is blocked so i dont add that one. Then inside of tile A store B, C, D (and not E) and then these will be used in pathfinding as potential movements. I have a couple more, if you don't mind, but perhaps the answers to the one above will also answer those If you look at our web: http://i.imgur.com/OvVs5ss.jpg Each intersection of red lines is a Node, and the red line itsself is the edge of the graph that connects 2 nodes. You can see that each node can have 1 or more neighbors, typical case for me is 4 neighbors. 1 Quote Link to comment Share on other sites More sharing options...
Botre Posted March 12, 2015 Author Share Posted March 12, 2015 (edited) here is someone open source walker. Dont take credit for his shit please lol https://github.com/Lem0ns/Walker/tree/master/webwalk/obstacles (once your done give me your source ) Oh very cool thanks! I'm just curious about them not sure if I'm going to write one, but if I did I'd probably open source it @Mysteryy: Thanks you sexy beast Edited March 12, 2015 by Botre 2 Quote Link to comment Share on other sites More sharing options...
VladBots Posted March 12, 2015 Share Posted March 12, 2015 A couple of questions: - What exactly is the role of the node in this scenario? Is it one walkable position of an area you feed to the pathfinder? Or do you feed all walkable positions to the pathfinder (this seems expensive though)? - To generate the graph, do you walk the surface and collect map data or do you just use a cache from the map and load all data at once? - Could you explain the word "web" ? What exactly is interlinked? The nodes? If so, why would you need a pathfinder if a relation is pre-established? I have a couple more, if you don't mind, but perhaps the answers to the one above will also answer those Think of a web as dots which are connected by lines, ideally you would want as few lines as possible in a web. Good practice would be to get an image of the RS map, paste it into paint and draw a web. I recommend the use of dijkstra or JPS Quote Link to comment Share on other sites More sharing options...
Mysteryy Posted March 12, 2015 Share Posted March 12, 2015 (edited) I would not recommend using Dijkstra for a web in Runescape. Using this will take much longer in most cases, as it will examine tons of unnecessary nodes. A* takes advantage of a sort of guided search using the heuristic, which points it towards the destination at all times. For anyone who needs a better understanding of them, i highly recommend watching this video: Edit: Also keep in mind that we will not be using blocks in our pathfinder, the graph will only contain walkable nodes, so you can compare more accurately the cases in the video where blocks are not in the way. Note how much faster A* is in those cases. Edited March 12, 2015 by Mysteryy Quote Link to comment Share on other sites More sharing options...
