Creep Spawn System cleanup

[sethmachine]

Hi,

So I implemented a functional creep spawning system not unlike that found in Pokemon. It basically has two parts:

a) a CreepRegion: a rect/region where if the player is inside, creeps will occasionally spawn from the region's table

b) a CreepTable: an array of possible creeps that can spawn (each CreepRegion gets its own CreepTable that it uses to look up which baddies to spawn).

I used a timer for each player that checks periodically to see if they are in a creep region (used an integer flag, -1 means they aren't so don't spawn anything).

My question is, what should I do to clean up the creeps say if

1. The player leaves the area

2. There are too many creeps

For 1) I am a bit concerned, since it could be possible other players might want to fight the baddies that spawned, so it would be awkward if player 1 was attacked by creeps, but player 2 engaged them. Then p1 leaves the region and suddenly those creeps magically disappear..awkward. Or do I make the creeps follow the player indefinitely (a bit hardcore though)?

For 2) I want there to be a challenging element, so players who refuse to kill units or take too long can get overwhelmed. But how do I know when enough is enough. And in the same line as 1), what if someone else wants to step in?

So do I keep track of the creeps each player ran into in their own private arrays, and when they reach their maximum creeps, I begin to remove some anyway, starting from the creeps that have been out the longest (and most likely the ones they have ran past and are not fighting). This doesn't solve the problem in 1).

Also, what happens if I call CreateUnitAtLoc, but the random loc I picked happens to be in a spot where a unit can't be made (e.g. water). Will that cause a leak, or will it be covered because I eventually clean up all the creeps anyway (the player will hit the max amount, and this "unspawned" creep will be cleaned up).

 

[Cokemonkey11]

You can keep track of how many players are used in a region with a counter

unit enters region -> increment counter

unit leaves region -> decrement counter

while counter > -1, do:

if (creeps already spawned) < (max creeps spawned() ) then

spawn random unit

then the function:

max creeps spawned ():

return min + player level * level factor + counter * counter factor

This is just an idea, there are many solutions to the problem though.

 

[Dr Super Good]

For 1) I am a bit concerned, since it could be possible other players might want to fight the baddies that spawned, so it would be awkward if player 1 was attacked by creeps, but player 2 engaged them. Then p1 leaves the region and suddenly those creeps magically disappear..awkward. Or do I make the creeps follow the player indefinitely (a bit hardcore though)?

Do not immediately remove creeps and instead despawn them (will describe later). Instead alter the maximum number of creeps down when ever a player leaves the region. If there are still players in the region then there will still be a creep limit > 0 but less than before the other player left.

For 2) I want there to be a challenging element, so players who refuse to kill units or take too long can get overwhelmed. But how do I know when enough is enough. And in the same line as 1), what if someone else wants to step in?

The limit system accommodates for this. When more players step in then more creeps can spawn and be active so they can be more over whelmed. When they leave creeps are not removed immediately and are instead subject to despawning.

When the number of creeps is greater than the limit, despawning occurs. This is a random process that chooses a monster and removes him from game every few seconds (some multiple of the spawn rate so that the change is gradual). To prevent the problem of "poofing" what would occur if the victim was truly random from the creeps, you instead only pick a random creep that is not visible to the players and not near them. When no players are in a region the number of creeps will gradually fall to 0, clean results. The gradual change also allows players to change their mind and come back to fight creeps without the area being completely creep free.

Both the spawn rate and the maximum count for a region should vary with player number. This means if a region has a lot of players in it they can be overwhelmed by a lot of creeps and will have a fast creep spawn rate to compensate for the faster killing potential.

 

[Meticulous]

Personally for the area exiting I'm a fan of creeps never chasing out of their designated area, and instead running back to where they spawned and gaining rapid regeneration so they can't just be repeatedly kited. To me it's the cleanest possible method.

 

[sethmachine]

What is the best way to check if a player is in vision of a creep? Would I not need to check over every player (so in order to remove a creep, it has be true for all players that it cannot be seen?).

 

[Cokemonkey11]

I think by in vision he just meant to check if they're nearby.

I suggest IsUnitInRange(), or a simple enumeration for the creep in question

 

[sethmachine]

Sounds simple. But what about when I make them. Right now they just appear near the player and are instantly aggroed. I'd like to make them appear sort of like Skyrim with random encounters--the random NPC/monster is usually in the player's path, but they don't see them spawn or appear out of nowhere.

This is simple for a single player (I just choose a location out of their vision, and then order the monster to attack them). But what if there are many players in the same area? I would have a difficult search problem, because I would need to choose a point which is not in vision of any of the players, and then from the points I choose, it might be the case none of them are 'remotely' close to the intended target player and the creep might get aggroed by somebody else on its way to its target.

Finally, what if (possible if I have a small region with rare monsters, e.g. in pokemon some pokemon only appeared from maybe a single square of grass!) the entire region is visible, and there is no point which is not in vision of at least one player. What do I do then (unlikely, but not impossible)?

I've already decided to drastically reduce player's vision (800 during daytime), but still I'd like to know the best way to do this.

Edit: Second problem

What about more constricted spaces, like dungeons, that might have narrow passages or walls? How on earth do I filter out points which are in what I claim to be invalid spots, e.g. on a dungeon wall or someother inaccessible spot? What's the standard way to do this?

 

[Dr Super Good]

If players share vision than testing sight at a location for any one of them will work since their vision is basically the same. It is only costly if each player has independent vision (no sharing) since then you will need to test against all players (who are in the region, no need to test ones that are not).

In your spawn table you could add a field for pop spawning. This means that they will not try and spawn discreetly out of sight and can spontaneously appear in front of the player. This can be used in the tables of very small regions where it would otherwise be impossible to spawn a monster as the entire region is in sight.

As for normal spawning. Simply try random locations inside the rects that compose any region. If the location is not visible then spawn, otherwise try again. Limit this search to 10-20 times per spawn cycle. If one cycle fails defer spawning until the next (which can be a fraction of a second later, as long as it is at least a frame delayed. If you want regions with full vision of (due to distributed player positions) to still spawn (pop spawning) then simply limit the maximum number of cycle tries to 3-4 before using any only random location which is likely inside sight range.

 

[sethmachine]

Well how do I check if a location is visible? I don't suppose there's a native?

function isLocVisible takes player whichPlayer, location whichLoc returns boolean
...
endfunction

Returns true if a given location is visible for the given player.

 

[Acutesharpness]

I would suggest you to set a limit to a each region, say that the noob region can spawn maximum of 20 and the big ones at maximum of 10 or so.. If you want to clean up then store them in an array every time you spawn, that way you can remove them if they are too messy. Well the way I would do it for the spawn is, example every 5 seconds, I would check if the map has a total of which amount of units of which type. Example the noob camp uses centaur as a type so for 30 centaurs found in the map I would stop spawning, else the spawn continues. Therefore, this system will not matter if the player kite the mob out of region since you already checked the whole map for it.

 

[Meticulous]

The other part of your problem can be solved with more complex level design. Place a lot of trees and other doodads with line of sight blockers so creeps can pop out of many unexpected places.

 

[Dr Super Good]

Well how do I check if a location is visible? I don't suppose there's a native?

constant native IsLocationVisibleToPlayer takes location whichLocation,player whichPlayer returns boolean
constant native IsVisibleToPlayer takes real x,real y,player whichPlayer returns boolean

Yeh as you can see their are 2. Not even sure why you needed confirmation since you can easily find them in any native list (I use the pre-historic Jass Shop Pro for this). No idea why you would want an adapter interface for them.

 

[sethmachine]

Well I do search vexorian's jass manual often for finding natives, just didn't actually think these natives existed.

But still in the worst case scenario I would need to run "isVisible" times proportional to the number of active players in the region (because it's an "or"), so it sounds like it's just as difficult a search problem as checking for all of them (I think "and" and "or" have same worst time complexity).

Not sure what is meant by "adapter interface?"

 

[Dr Super Good]

But still in the worst case scenario I would need to run "isVisible" times proportional to the number of active players in the region (because it's an "or"), so it sounds like it's just as difficult a search problem as checking for all of them (I think "and" and "or" have same worst time complexity).

Only if they do not share vision. With vision shared then you only need to test one of them. In either case as long as you try a reasonable number of points per attempt it should be fine.

 

[Cokemonkey11]

(I think "and" and "or" have same worst time complexity).

Haven't tested it myself, but I do recall or-ing of multiple values getting short circuited.

Consider:

if <true condition> or <false condition> or functionCrashMap() then
    //These actions should occur since the or were short circuited after the initial true condition
endif

 

[sethmachine]

Only if they do not share vision. With vision shared then you only need to test one of them. In either case as long as you try a reasonable number of points per attempt it should be fine.

Oh I see now, that's very clever. It counts the shared vision. Thanks for clarifying this.

@cokemonkey well in theory "and", "or" should take the same time to check in the worst case shouldn't they? If you have "n" conjuncts, you have to check the truth value of each one for "and," and as soon as you find a false you're done (worst case is they are all true). Same for "or," as soon as you find a true they are done (worst case is they are all false).

 

[Cokemonkey11]

@cokemonkey well in theory "and", "or" should take the same time to check in the worst case shouldn't they? If you have "n" conjuncts, you have to check the truth value of each one for "and," and as soon as you find a false you're done (worst case is they are all true). Same for "or," as soon as you find a true they are done (worst case is they are all false).

Yes you're right, forgot about that