Help wanted: Source Keepers overhaul

artch

Recent events (see our Status Page) have shown a major flaw that may cause a lot of performance issues in some circumstances. Source Keepers are designed to act like regular NPC users. They have some AI logic, but the real problem is not in their AI, but in the NPC users themselves. Since all SK rooms cannot be placed into one userland script for performance reasons, the game runs every SK room as a separate user, thus creating some overhead.

What we would like to do now is to get rid of userland SK code completely. Instead of running their AI in runners, all logic will be handled in processors directly. It means there will be an AI-like module in processors that create some intents for a SK creep, and then intents are processed as usual.

One thing that complicates this task is path finding. The need to find a walkable path makes it harder to move this logic to processors. This is why we propose to change SK movement logic to the following: a Source Keeper appears at the lair tile and then crawls to the energy source tile, moving right through walls. Then it sits on top of the source defending it. This change would allow us to eliminate the need of dynamic path finding, a path for every source keeper from the same lair will always be the same. UPD: Path finding will go through plains as usual, but it will be non-dynamic, i.e. the path is calculated once and then reused. If a SK is blocked, then it will stuck until it kills the blocking creep or dies.

OK, and now is the interesting part: we would like to outsource this feature to the community. The author of a successfully merged Pull Request will receive 5 Subscription Tokens.

Specification for this task:

Create new processor-side AI-like module that creates intents (move,attack,rangedAttack,rangedMassAttack) for Source Keeper creeps in active rooms.
When a creep is created, it should be given with a path from the lair to the source.
When this path is generated and how it's stored is something that we bring to discussion. It may be stored in either lair or creep DB object. Pathfinding may be done either when the creep is created, or once per lair in case if it's absent in its DB object. You can use either @screeps/pathfinding module in processors, or (preferably) implement your own simple algorithm to find these 2-3 steps from the lair to the source.

PostCrafter

How about moving the keeper lairs right on top of the sources? This will remove the need to find a path at all and also won't require move logic in the source keeper code. Additionally this doesn't cause any issues for cases where the source is located on a single wall tile - I don't have an example for such a case in a source keeper room, but I certainly saw those in normal rooms.

I would like to pick up this challenge, but unfortunately I don't have a lot of time this weekend.

artch

@postcrafter It may be an option in some edge scenarios, but not generally. It looks more funny when they crawl along walls like spiders.

Another option would be not to move lairs, but to allow keepers move through plain tiles as well (with wall tiles being preferable), but this would introduce issues to some players with code vulnerable to creeps stacking on one tile, since we have no dynamic path finding here.

eduter

SKs could move on a straight line towards the source, through any terrain, with no path finding, but still subject to collision with other creeps, which would be targeted. Optionally, they could try to go around creeps by picking an adjacent direction, if that is not blocked. Lairs that would cause SKs to move through walls that are not adjacent to walkable tiles could be moved to satisfy the criterion of exposing them to melee attacks at all times.

Kasami

Just wanted to add a reminder about that this concerns minerals too. And that those minerals have an extractor which may or may not effect things.

artch

@eduter "Straight line" could be generated differently depending on the algo, there's no guarantee that every step will be exposed. And we'd like to move as less lairs as possible.

artch

@kasami Exactly, minerals are treated as sources in this case.

Dissi

A simple getDirectionTo() could eliminate the need of path finding.
SK's currently are blocked by player creeps anyway, they will hammer on the thing that's in the way.

artch

@dissi Simple getDirectionTo wouldn't meet this requirement:

Every wall tile should have at least one adjacent plain tile (in order for the creep to be exposed to player melee attackers at any given moment).

SK's currently are blocked by player creeps anyway, they will hammer on the thing that's in the way.

What do you mean blocked? Currently they can redo pathfinding if they are blocked, i.e. it's dynamic (with reusePath:50), isn't it?

Dissi

@artch said in Help wanted: Source Keepers overhaul:

What do you mean blocked? Currently they can redo pathfinding if they are blocked, i.e. it's dynamic (with reusePath:50), isn't it?

Yes, basically it means they'll probably be stuck for 50 ticks, and recalculate the path.

@artch said in Help wanted: Source Keepers overhaul:

Every wall tile should have at least one adjacent plain tile (in order for the creep to be exposed to player melee attackers at any given moment).

If we want to keep it as simple as possible it might be better to only do a getDirectionTo and move that way. And yes, if we want to have the move over the wall requirement it wil require additional logic and getDirectionTo will not suffice.

artch

@dissi So we have to decide do we want to always keep them exposed, or some periods of inaccessibility (and thus invulnerability to melee attacks and no valid path with range:1) is fine. We also should consider that these periods may be very long in case if some MOVE parts are dead.

eduter

@artch It seems to me like you will have to pick 2 out of these 3:

keep SKs exposed to melee attacks at all times
make SKs' movement as simple as possible
keep lairs where they are

artch

@eduter Exactly. Very interested in community opinion on what's more important.

PostCrafter

@artch Mind sharing what exactly you think the issue with moving the Pathfinding to the processor is? I'm still fiddling with the server code to understand how exactly NPCs are integrated into the flow of the game, but calling the pathfinder differently seems like a fairly small issue to me, so maybe I'm missing something here.

Also what exactly is the overhead here? Is it the creation of the vm for each SourceKeeper or the setup of the API wrapper usercode has? Is it an option to just remove the vm layer for NPCs?

artch

@postcrafter Runtime overhead is created not only by vm module itself, but by many other factors: working with inter-cluster user execution queues, fetching database queries, managing separate runtime processes with their own timers, etc.

Adding full path finding (i.e. feeding full room grid to real A*) to processors is inappropriate since processors are meant to be very fast, and a single heavy path finding call could be longer than an entire room processing cycle. Also, @screeps/pathfinding library has some overhead like initializing heaps, and doing that in processors is no good. Better to make something simple instead.

deft-code

I think it should be possible to keep the SK movement very simple (local greedy search). That means an SK might get stuck in a loop and never make it to the Source or Mineral, but it should be rare so it won't ruin the fun. It might even enhance the fun with crazy techniques to send SKs on wild paths.

This would keep the SK vulnerable to attack (same movement restrictions as any other creep they can't move onto walls, etc). The movement code is dead simple move in dir of src, if blocked by wall, move diagonally to src, if diagonal blocked by wall then move random. The same brain dead code can be used to pursue player creeps if we want to allow that. SK lairs don't need to change and could be consolidated in the future with no changes.

All this assumes that the processor does some intent validation. E.g. I believe it is the processor that decides which creep win when two creeps try to move onto the same square during a tick.

I think targeting creeps might be a harder problem. I believe the LOOK and FIND indexes won't be available in the processor. How will the creep discover which creeps are in the room with it? Without the LOOK indexes it might be very expensive to loop over all creeps in the room checking for range.

artch

@deft-code Making LOOK and FIND indexes requires looping through objects as well, so there's no difference, either NPC processor or runner should do that anyway.

We're now debating whether it's viable to leave their movement by plain land as usual, but without dynamic path finding. I.e. the path is calculated once and then reused, and if the keeper is blocked, it will stuck until it kills the blocking creep or die.

Eiskalt

@eduter said in Help wanted: Source Keepers overhaul:

@artch It seems to me like you will have to pick 2 out of these 3:

keep SKs exposed to melee attacks at all times

make SKs' movement as simple as possible

keep lairs where they are

I would take the first two options and move some lairs:

keep SKs exposed to melee attacks at all times
make SKs' movement as simple as possible

A vast majority of players will not even notice if some lairs are relocated.

artch

OK, the task specification has been changed. Let's settle on this:

leave their movement by plain land as usual, but without dynamic path finding. I.e. the path is calculated once and then reused, and if the keeper is blocked, it will stuck until it kills the blocking creep or die.

The first post is updated.

Dissi

@artch said in Help wanted: Source Keepers overhaul:

leave their movement by plain land as usual, but without dynamic path finding. I.e. the path is calculated once and then reused, and if the keeper is blocked, it will stuck until it kills the blocking creep or die

This makes the logic a lot easier to implement. I also thinks this looks a lot like the current implementation.