ID:2343129
 
Applies to:Dream Maker
Status: Open

Issue hasn't been assigned a status value.
So, a lot of SS13 servers (I'd hazard to say nearly all of them) have A* implemented in some way or another. Unfortunately, due to various factors that are slightly over my head, A* has some amount of enormous overhead when used to find something more than 5 turfs away from the source. Given the versatility of such a function, I would absolutely adore to see it in byond in a manner that isn't outright unusable in most cases.
A* is already built in, although not in a way that provides fine access. I don't see a way for a finer-grained built-in approach to be feasible, but I'd be surprised if there weren't ways to improve the A* as implemented in soft code. I implemented a modified A* in SotS II that was relatively performant for short hops, so I'm sure making the soft code faster is approachable.

But overall I'm not entirely clear on what you're asking for in this feature request. What specific changes or options are you hoping for that would, in theory, augment or replace the soft code versions?
Maybe improving the built-in variant when presented with paths longer than 5 tiles? All of the functions in DM work great, until you actually give them some distance to work with and they take an absolute dump in performance.

Pathfinding isn't all that useful if you can only calculate four tiles at a time, and hops tend to get inaccurate after a few when you recursively call the built-in functions with short ranges. Most of the time they end up walking in a circle or not finding a path resolution at all and not moving at all.
I'd personally love to see a better implemented A* pathing placing into Dream Maker. It's the reason why my Dungeon Master Game was/is a laggy heap of joy.


It's also why I haven't remade the game in all seriousness, because there's a lot of overhead from adding your own one which I feel could probably be avoided if added straight into the engine.

A good example is Game Maker Studio, you can get it to work really well even on large maps. Granted the engines differ considerably, but it would be an amazing feature to have; to be able to send a mob through a maze more than twice the distance of world view.
I'm honestly not too sure on what is needed, I'm not too deeply ingrained on why, or the details, but apparently there's weird overhead involved with coding your own.

https://github.com/tgstation/tgstation/blob/ a2d5b2a43b10db1a5a22377ebdd7d9c46d8666a1/code/__HELPERS/ AStar.dm being an example of the most optimized version of A* in an SS13 codebase that I know of... Which exhibits the issue of lag over 5 turfs. I was told byond had it internally, and was clued in with some basic information on this, but could not quite figure out what proc held this sort of pathfinding.
its actually not optimized since it uses a list search where a direct var access could do. We had to choose between allowing multiple active astar jobs so that 1 long path find doesn't block a bunch of small hops, and performance.

One major suggestion I could make off the bat is to avoid using datums for this purpose. In my A* implementation in SotS II, I use a list which contains multiple ordered items (e.g., 3 values in a row) and another list for indexing, and sort the nodes via heap sort.

Directly accessing an item in a list is much faster than accessing a datum var, so there's a place you can make big gains.
Here's a rough description of the data storage I use for A* pathing in SotS II:

The algorithm uses a /pathheap datum that stores info about nodes. Each pather datum (/pather3 in my case because there are a couple of kinds) uses two of these heaps: one for open nodes and one for closed nodes.

The /pathheap datum has two lists: heap and data. The data list consists of ordered sets of data: the cost plus heuristic, and the heuristic alone. The heap list is associative, where heap[turf] is the index of the turf's data in the data list, and the heap list is heap-sorted by lowest cost+heuristic--which is to say, the cheapest node is always in position 1; for any node at position k, its children at k*2 and k*2+1 have a higher or equal cost+heuristic.

The position of the info in the data list never changes as long as the node exists in the heap. The only real permutation that has to happen is tot he heap list itself, which is just looking up the cost of a node and bubbling up or trickling down as necessary to move it into the correct position.

As with any heap sort, when you remove the top node (index 1) you just find the node at index heap.len, move it into position 1 instead, and trickle it down by swapping with the cheapest child repeatedly until it has no cheaper children. Adding a node just puts it at the end of the list and bubbles it up by swapping with a more expensive parent repeatedly. Since all the algorithm cares about is getting at the node at the top of the heap, this is a very efficient way to sort the nodes.

Looking at this code again I can see several places for further optimization, especially with newer language features. But basically the deal is that with a heap you always have easy access to the cheapest node, and using the data list avoids having to use datums to store info.
Sorry for a bit of necro, but here are some oldies you may not have checked out.

http://www.byond.com/developer/Kuraudo/libpathfinder
http://www.byond.com/developer/Theodis/Pathfinder