Thread: A* pathfinding

Originally Posted by Inside Sin

So how are you sorting the paths from longest to shortest. Like I said, I am unsure as to what method you're using as an A* search, but afaik you won't be using a single 2D array across the implementation.

A* doesn't find every possible path to a point, it only finds one, so I'm unsure what you mean with "sorting the paths from longest to shortest", it does require you to keep the nodes in a sorted priority queue if that's what you're thinking of (which can be an array also...)

Originally Posted by Scu11

A* doesn't find every possible path to a point, it only finds one, so I'm unsure what you mean with "sorting the paths from longest to shortest", it does require you to keep the nodes in a sorted priority queue if that's what you're thinking of (which can be an array also...)

So there's no sorting in a sorted priority queue? ok.

Originally Posted by Inside Sin

So there's no sorting in a sorted priority queue? ok.

You said "sorting the paths from longest to shortest", that is nothing like what the priority queue of nodes is doing/for.

Furthermore the priority queue can be backed by an array, so back to your initial point I don't see why you think the algorithm can't be backed by arrays and are at all detrimental to performance.

Originally Posted by Scu11

You said "sorting the paths from longest to shortest", that is nothing like what the priority queue of nodes is doing/for.

Furthermore the priority queue can be backed by an array, so back to your initial point I don't see why you think the algorithm can't be backed by arrays and are at all detrimental to performance.

I never said that you can't use an array, I said that you should be using a list whenever the requirements are not array specific. I also never said the result was detrimental, I said the change is ideal in the step towards efficiency.

Originally Posted by Scu11

there's no searching or insertion involved (other than population which should be done at server startup).

So you're saying there is sorting now?

I really have absolutely no clue what you're trying to say here unless we're talking about different things.

A* pathfinding is calculated using best-first search. From my knowledge the use of closed and open sets is widely used in writing an efficient method and although I have only done this in C#, I am sure it is done the same way in Java. I am also aware that edges have weights and perhaps because we're talking about RuneScape here that each edge is of uniform length thus complicating the comparison.

I understand I'm not well-informed on what your code is or what it does so perhaps you'd like to message me a snippet so I can understand what you're trying to say?

I said that you should be using a list whenever the requirements are not array specific.

The requirements do favour arrays though, you want to be able to check if you can use an edge of a tile to traverse through in constant time; arrays are ideal for this. Lists (especially linked lists) are not ideal for this as you have to iterate through them which is not constant time. An array list would be okay but this is just backed by an array still and offers no performance enhancement.

I said the change is ideal in the step towards efficiency.

You say that using arrays aren't detrimental to performance but then say moving away from arrays are the right step towards efficiency? I don't follow.

Originally Posted by Inside Sin

So you're saying there is sorting now?

No? The word sort wasn't even in the text you just quoted. My point in that text was related to searching a list for a tile's flag vs looking it up in a two dimensional array, this point was entirely unrelated to the priority queue.

so perhaps you'd like to message me a snippet so I can understand what you're trying to say?

Not really, this talk is about A*, my implementation isn't any more specific than the one included in the main post.

Alright I think the issue here is that you said you used arrays and bitshifts and I automatically assumed you were simply using a 2D array as well as seperate arrays to store open and closed sets. This is where I think a list would come in handy, not the 2D array, given in theory RS2's world is a 2D plane in it's simplest form. I am just unsure how you think you can get away with no sorting in an A* pathfinding implementation, by unsure I mean I don't know and I am only under an impression that it is not entirely possible.

I can't remember how significant or in which area of the data structure a List outperforms an array but I am sure it does (we're talking about the closed and open sets here, which I am under the assumption sorting is required).

I agree that linked lists alone is a significant error in the development of this algorithm.

Originally Posted by Inside Sin

Alright I think the issue here is that you said you used arrays and bitshifts and I automatically assumed you were simply using a 2D array as well as seperate arrays to store open and closed sets. This is where I think a list would come in handy, not the 2D array, given in theory RS2's world is a 2D plane in it's simplest form. I am just unsure how you think you can get away with no sorting in an A* pathfinding implementation, by unsure I mean I don't know and I am only under an impression that it is not entirely possible.

I can't remember how significant or in which area of the data structure a List outperforms an array but I am sure it does (we're talking about the closed and open sets here, which I am under the assumption sorting is required).

I agree that linked lists alone is a significant error in the development of this algorithm.

Yeah I was never talking about using arrays for open/closed sets, I was talking about using arrays to store the edges/nodes in the graph you're searching for paths over.

Also I never stated you can't get away with sorting, I said there's no searching/sorting involved for checking if an edge is usable or not when using a 2d array to store the edges

Originally Posted by kLeptO

For those who think that client-sided path finding is a good idea.

Cons:

• You are relying on client-sided resources.
• You are relying on client latency. (you can't expect latency to be consistent)
• Generating paths will take longer: receive message, generate path, send reply. (assuming client runs on 50ms tick, even with 0 latency it will take 50ms)
• What about cases when client disconnects? Would that delay npc following until new client is found and path is generated? (bad gameplay experience)
• You are vulnerable to path modifications. (let's send this boss to lumbridge)

Pros:

• Saving 5ms processing time server-side!

In regards of list vs array discussion, arrays give you faster access to elements, lists give you faster insertion and expansion. It really depends on situation which one you want to use. For example for something like path finding you might wanna use mixture of both, arrays for looking up clipped tiles (you need fast way to figure out which tiles are walkable) and lists for saving path (you don't know how long path is gonna be, need data structure that is easy to expand). For something like A* though, you will often see binary heap (priority queue) being used (quite often binary heaps are backed up with an array).

I ****ing love theory based on stacks. My first lesson in C++ efficiency was the best lesson I've ever had. I had one unit devoted to Data Structures and Algorithms (literally that's it's name) and it was amazing. I felt like I was such a dev-pleb before hand.