Webwalking

[Botre]

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

 

 

 

[VladBots]

essentially you just need to build everything into a weighted digraph 

[Mysteryy]

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

[DragonAlpha]

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.

[Botre]

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

[Joseph]

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)

[Mysteryy]

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. 

[Botre]

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

[VladBots]

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

[Mysteryy]

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