Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[TheBiggerFish]

Sounds like it is, not that I'd know...

[Bauglir]

If it's a DAG you might be able to do your updates starting at nodes from the bottom up, but I imagine you've thought of that and it isn't.

EDIT: Maybe you could have them move without any knowledge of whether another node is occupied, and then only check validity after every entity has made up its mind? Then just have entities with invalid moves make new choices with the failed one ruled out and repeat until every entity makes a valid choice or runs out of choices. This does allow them to switch places, but otherwise might offer the behavior you want?

EDIT EDIT: Although on further reading, "following" isn't just something that should be allowed, but something entities should specifically be able to choose to do. In that case you'd probably need to allow each entity to track a list of other entities upon which their behavior depends, and mark them as having invalid moves until each entity on the list has made a valid move.

[EnigmaticHat]

Man, it's surprisingly hard to add following behavior for entities pathfinding on a connected graph. Each node on the graph can only hold one entity, so when the entities are pathfinding I need to set nodes which already contain entities as impassible. This means that an entity which is trying to follow one node behind another keeps "bumping into it", but only if the following entity takes its turn before the followed entity.

The obvious solution is to set an entity's current node to passable if it's going to be moving this turn, but whether an entity will move could depend entirely on a third entity which may or may not block its path depending on whether that entity has moved already and AUGH

This is reminding me of network programming

Give every entity a priority based on how important/powerful/whatever it is (not sure the context here).  Everything makes their moves as if there are no other entities on the graph; if a lower priority entity moves onto a higher priority entity the move doesn't occur.  If higher priority moves on top of lower priority they swap places.  Stationary entities count as the lowest priority to prevent a higher priority entity blocking a path forever.

Followers skip their move and instead whenever the target attempts a move it causes the follower to also move according to the normal logic.

[Reelya]

A couple of quick and dirty hacks are possible, such as storing a "prevNode" for the followed entity, and have the follower path towards that. But that would preclude the follower from finding more optimal paths in case there is a better route.

For EnigmaticHat's "priority" system, the best way would be to make a separate array of all "mobile" entities, and ensure the things in that array are ordered followers-after-followed, so you don't have to determine each entity's priority each frame, you just do the moves in the correct order. Stationary units just aren't in the priority-queue and never get processed, and a follower will never "bump" because they always get processed after who they are following.

[Bauglir]

Yeah, EnigmaticHat's got another strategy, although I'm not sure that the array Reelya suggests necessarily works. If the graph isn't acyclic, one can imagine a sort of circular conga line that prohibits an array being properly ordered, especially since it can have branches sticking off it even if one entity can't follow multiple other entities. But I'm very tired, and I may just be missing the ways of handling those two things efficiently.

I did forget to include a priority system in what I suggested, though. I think that if you don't have an existing priority, you could just randomly determine which entity gets to move into that node and have the others get marked as having invalid moves, kinda like a random backoff scheme (there's that networking thing you mentioned, hah). And if they're not moving aimlessly you could also get a little more elaborate and mark as invalid nodes that don't fit a heuristic, or even "invalid unless i've already made enough invalid moves". It all really depends on what the application is.

EDIT: Basically, instead of trying to determine an optimal set of moves, just throw moves at the wall and see what sticks. Lots of retries may be faster than analysis, and is usually easier to program. Is what I'm suggesting, anyway.

[Reelya]

The shape of the graph has nothing to do with the problem.

Gatleos's problem was stated as an entity follows another entity one node behind, and there should never be a gap or another entity gets in the way. Moving entities at random wouldn't achieve that stated outcome.

What I said about ordering the moves via an index would do the job. If you make sure each entity moves directly after what it follows, then nothing would ever get between the two. The order of any other entities is irrelevant, as long as the "follower" is processed immediately after the "followed". Actually, this is exactly the same as the priority system of EnigmaHat, except instead of having to do a search for highest-priority, then next-highest-priority, etc, every single frame, you'd be pre-ordering the moves in the index (reordering some ints in an array is also very fast).

Same outcome, but much faster and gives you more control (since you can ensure that a follower is processed immediately after the thing it follows). No need to compute "passable" values differently this way either.

[Bauglir]

Right, I just meant how do you handle cases like "A follows B follows C follows A, and also D follows C". I brought up the shape of the graph because such a case can't happen if there are no cycles (I think), but that was jumping ahead and I should've just directly stated what I had in mind.

Although I've clearly misunderstood because I didn't realize that "there should never be a gap or another entity that gets in the way" was a necessary feature - I just thought that the problem was that you get different behavior depending on the order in which they were updated, and that was undesirable. Reading it again, I'm still not sure that the conditions you describe are clearly there, but they certainly could be - don't mean to speak for Gatleos but I don't get the impression that there was any intent to give a clear specification.

Sorry if I came off as dismissive, though. That wasn't the intent, so if I did then I fucked up. I think we're solving different problems?

EDIT: Wait, my suggestion doesn't solve that case either. Shit, I suck.

EDIT: I should clarify that I never suggested moving at random, I suggested deciding priority at random if there's no existing scheme for that. That said, since I speculate that you'd want a circle to spin in place rather than sit in deadlock, what I said about implementing following behavior as "Wait for the followed entity to move before moving" is stupid, and you'd want it to be "Move toward the followed entity, even if that puts you in the space they're currently in". That solves my previous edit pretty simply. If the followed entity doesn't move, the follower will get bounced back during the check for validity, and if the followed entity does move then the follower is guaranteed to have moved into the node immediately behind the followed. Provided everything moves one node per step, anyway, which I guess was never stated.

[cerapa]

I had a similar problem with a hex grid of armies marching towards eachother.

The solution I found was to have a flag for each unit which said whether they had finished their turn and then...I think it's best described as a list

If the unit has already been calculated, you just back off. Otherwise set the flag for having been calculated at this point, so you don't get an infinite loop.
Then you find a path. Units that have moved are obstacles, one's that haven't aren't.
Then you step backwards from the path and if there are any units, you do their pathfinding first.
Then check the path for obstacles. If there aren't any, move the unit, otherwise go back to the step of finding a path. Rinse and repeat until you have a clear path or direction to go.

Basic principle is that the units in the way get priority and move out of the way.
In my case, I just had a vague direction that they wanted to go and so they calculated a path that was basically just a couple of hexes long. With longer paths, I think a decent modification would be to make it ignore units that are further than a single move. So they have a longer path that ignores units, and shorter one where they don't.

[itisnotlogical]

I've discovered a blatant lie in Game Maker's documentation. According to the documentation on rooms, the Instance Order is a list of which objects should be created in which order, so every object in the room will respect this list when being created.

That'd be great, were this actually true. It's not. While the documentation says this should happen:

Code: [Select]

first_instance_in_list:
script1_in_create_event();
script2_in_create_event();

second_instance_in_list:
script1_in_create_event();
script2_in_create_event();

What actually happens appears to be this:

Code: [Select]

first_instance_in_list:
script1_in_create_event();

second_instance_in_list:
script1_in_create_event();

first_instance_in_list:
script2_in_create_event();

second_instance_in_list:
script2_in_create_event();

This would be less frustrating if I didn't promise my employer that I'd have a video done by Sunday, and I keep running into problems with the documentation either being too vague or just outright lying about how the software basically works.

[Gatleos]

Some very good suggestions, thank you.

However, I now realize that the problem isn't just getting entities to follow each other. While a case where one entity is specifically told to follow another is possible, I also need to ensure entities moving through cramped spaces won't block each other. That is, one might not be following another, but it still might need to follow closely behind in single file. Like this:

Spoiler (click to show/hide)

White line is the highlighted entity's path, those white hexes are impassable. The other entity (on the right) has an identical path to the same destination. My goal is to get one or the other to get blocked and wait for a single turn, then follow behind the one that wasn't blocked, so that both entities get there in the smallest possible amount of moves.

I guess the most sensible thing for an entity whose path is blocked to do is to wait for one turn, then recalculate their path if the hex isn't vacated after that. That way, entities don't calculate some crazy-long path just because their next move was blocked by something else, but they won't sit there forever waiting for an opening either.

Now I just need to figure out a way to implement it. I also need some kind of priority system, so the same entity doesn't get repeatedly preempted before it can move into its next hex. This is reminding me of my operating systems class and process schedulers now.

[jaked122]

Why does it need a priority if all the entities that aren't blocking each other are the only ones taking initiative? Why not round-robin? Each gets to go once prior to going again?

[monkey]

Flow Fields ?
https://www.youtube.com/watch?v=jA2epda-RkM
http://leifnode.com/2013/12/flow-field-pathfinding/
https://www.youtube.com/watch?v=arx064_I9ck&t=280

[Bauglir]

Yeah, so I'll spell out the idea I had in mind, which I think also handles cases like yours. I'll do the steps in a monospaced font so I can indent neatly.

You have a map of hexes, some of which are impassable, say because of mountains. Additionally, some hexes may be temporarily impassable, for instance because they're occupied by another unit. You should also decide on a priority system. For instance, maybe bigger units block smaller ones. Or maybe a speed statistic should decide who "got there first". Alternatively, you can use a random number generator to assign priorities each time a conflict occurs.

1. Each unit plans a route. They plan around permanently impassable hexes, but they ignore temporarily impassable ones at this step.
   
2. Each unit takes one step along their planned route. Temporarily allow each hex to hold any number of units, but do not update anything other than position. For instance, don't draw their new positions to the screen yet.
    a. Each unit moves independently of other units, and as above they may take their moves in any order.

3. Check each occupied node for conflicts. There are no doubt ways to optimize the number of nodes you actually need to check, but this is the simplest. A conflict occurs when, after step 2, two units occupy the same hex. Only the highest-priority unit remains in its new hex. The others are moved to the most recent hex they occupied that didn't cause a conflict.
    a. Note that a unit getting bounced back may cause a new conflict if another unit moved into its old hex. You may want to handle resolving such conflicts differently so that you don't need to have a memory of each unit's move history. For instance, if the bounced unit also gets bounced out of its original hex too, it might wind up in the nearest unoccupied hex.
    b. If a unit gets bounced out of its original hex, it should keep a memory of all the impassable hexes it tried to occupy, so you can't just have them give up after six failures.

4. Each unit that was bounced back marks the hex it tried to move into as impassable until the next round of movement, but only that hex.

5. Each unit that was bounced back plans a route, as in step 1. If there are no moves that get it closer to its goal, it plans to stay in its current hex.

6. Each unit repeats steps 2 through 5 until it successfully moves, until it is adjacent to no passable hexes, or until it decides to stay in its current hex.
    a. Because it's possible for a unit that has met one of these conditions to wind up in a conflict with a unit that has been bounced back far enough, it is important not to forget about them entirely yet. You can forget about a unit when it and all units with higher priority than it have met one of these conditions, though, and I'm pretty sure this is guaranteed to terminate eventually.

Pros:
I'm pretty sure this system models your scenario correctly. Whichever unit has lower priority will get bounced back, decide to stay put for one turn, and then begin moving again.
Allows units to trade places if they're heading opposite directions. Each will move into the other's hex, but by the time conflicts are checked for they're already past each other.
Because each unit plans independently, it doesn't need to coordinate with every other unit to know where the others are going to be after moving. This means that large numbers of complicated routing rules don't blow up the computation time.
Because movement success is independent of the order in which moves are made, it avoids the classic Tabletop RPG problem of the thief who's uncatchable if they went before you but who can't escape if they went after (or, alternatively, the stuttering chase where you leave a gap between them if they move in the wrong order but not if they don't). (@jaked122 - this is why priority is necessary, if I've understood your question correctly)

Cons:
Needs a bit more elaboration to handle varied movement speeds - for instance, if one unit moves 2 hexes per turn and the other only 1, the fast one could leapfrog or do some other weird stuff.
Maybe you don't want units to be able to trade places.
Pathological cases with densely-packed maps can make it take a very long time to terminate.
Occasional weirdness, illustrated below.

I bolded that because that can be a serious problem if you predict lots of densely-packed unit formations, but if you don't then I like this approach.

Note that a possible sequence for a given unit is:

1. Move
2. Win a conflict, so stay in new hex
3. Lose a conflict, so get bounced back to starting hex
4. Decide no other profitable move, so try to stay in starting hex
5. Lose a conflict, so get bounced somewhere else
6. Move back to starting hex
7. Win a conflict because the higher-priority unit that bounced it out was, itself, bounced there and so moved out to be replaced by another, lower-priority unit

Assuming it never gets bounced out again, it'll stay there because it successfully moved in steps 6 + 7. A similarly complicated set of events might even clear up its original target hex, but it won't have the move to try and occupy that one - that's the weirdness I was referring to. The probability should be very low, but it is something to be aware of.

[EnigmaticHat]

Spoiler (click to show/hide)

...may I ask what you're making?

[jaked122]

...may I ask what you're making?

I'm not him, but it's either a strategy game on a hexagonal grid, an rpg on a hexagonal grid, or a bunch of hexagonal cells with a couple goombas in one.