search

tgstation / rust-g

Rust based libraries for tgstation
MIT License
28 stars 100 forks source link

Add an a* pathfinder #113

Closed BraveMole closed 2 years ago

BraveMole commented 2 years ago

Returns the shortest path in a static node map. That is made for TGMC wich uses manually placed nodes for pathfinding.

Benchmark : image That's the average number of path computed in one second, out of 30 runs with random nodes. Size of the node map is roughly 800

On average 32 times faster than tgmc a* implementation. Another possible comparison is with TG's JPS system, and according to the benchmark done here it's 7000 times faster (https://github.com/tgstation/tgstation/pull/56780). Not exactly the same use cases though

AffectedArc07 commented 2 years ago

So to be absolutely clear.

This is for static maps so things can pathfind through yes?

BraveMole commented 2 years ago

So to be absolutely clear.

This is for static maps so things can pathfind through yes?

Yeah, you need to prenode.

AffectedArc07 commented 2 years ago

So to be absolutely clear.

This is for static maps so things can pathfind through yes?

Yeah, you need to prenode.

Ok so to ask the incredibly dumb question.

If we need to pre node, why don't we just pre path for even more performance?

BraveMole commented 2 years ago

If we need to pre node, why don't we just pre path for even more performance?

Typical map has 1500 nodes, so that's about 1 million paths to compute and then save. I'd say it's not worth it.

Plus in TGMC system you can place additional goal nodes that will link to the node map

Mothblocks commented 2 years ago

A lot of this code scares me. Lots and lots of unwraps, and I highly doubt mut_static is a thing we want.