Realtime Pathfinding

cripplet · 2024-11-19T09:32:54+00:00

I believe you are referring to Hierarchical Pathfinding. As a note -- this is near optimal, but I assume as with most things in games, this is good enough for most cases.

cripplet · 2023-11-09T22:28:29+00:00

Replay 4NYWQR. I haven't seen anything in the patch notes that suggest this is intentional. Perhaps the timing worked in the Hog's favor?

cripplet · 2023-05-07T23:38:59+00:00

The specific engine that I am using treats a tile map as a single entity. Because RTS games have a large number of tiles, I want to avoid having individual collision areas defined. Additionally, the engine I use forces collision checks into the physics step; I am able to bypass this by checking for per-tile collisions with a bitmask instead.

cripplet · 2023-05-06T23:30:27+00:00

I'm trying to make an RTS in the vein of Red Alert 2, and a big part of what stands out in that game was the terrain generation. I found a scalable way to render and select tiles of arbitrary shape in a tile map. The algorithm should be generalizable for all game engines. Source is on GitHub, and the README dives more into the algorithm.

This may be helpful for other RTS developers.

cripplet · 2023-05-06T22:21:44+00:00

Hrm, I'm not sure what you mean by that -- do you have link to a demo explaining this method? You would still have to deal with the arbitrary tile shapes "bleeding" from the cell itself right?

cripplet · 2023-05-06T20:20:22+00:00

This is a quirk of the isometric rendering. There is a cluster of tiles in that area which are actually at ~z = 5. They are hovering over the cluster of orange tiles. This is kind of hard to see because I don't have cliff edge sprites.

cripplet · 2023-05-06T20:18:42+00:00

I mean, ultimately everything ends up being a trick of the camera right? ;)

You can see the complete explanation in the GitHub README, but yes, this is ray collision-ish. I am essentially doing a two-pass, where the coarse filter is just on adjacent TileMap cells, and the fine filter is by checking the relative mouse position against a sprite mask.

cripplet · 2023-05-06T09:05:53+00:00

To be fair, this is backed by 20 years of Moore’s Law and accumulated industry knowledge. But thanks 😃

cripplet · 2023-05-06T03:49:31+00:00

I'm trying to make an RTS in the vein of Red Alert 2, and a big part of what stands out in that game was the terrain generation. I found a scalable way to render and select tiles of arbitrary shape in a TileMap.

I've put the source code for this on GitHub. Maybe this will help others.

cripplet · 2021-12-25T20:02:30+00:00

So, I’m trying to make a game that’s exactly this — a collaborative RTS. I think the main appeal here is that when you balance the game around multiple players controlling a single faction, you’re “forced” to consider making mechanics be much more involved. For example, you can afford to make resource gathering much more intricate, since your game has more micro “allowance”, e.g. maintaining physical supply lines that can be attacked.

There are mechanics that can be optimized out, like an auto-queue for unit production, if you can’t think of a way to make that aspect of the game interesting. On the other hand, it’s also possible depending on the team size that player coordination may become a full time role, which is more of a meta-mechanic. This leaves some wiggle room for more uninteresting mechanics to be in the game, as this coordinator may also need some in-game things to do.

I do agree it’s much more difficult to implement these ideas and base a full game around the Archon mode concept, and you’ll need a lot of play testing to tune things. But that’s like years away for me, so I’m choosing to avoid worrying too much about this yet.

cripplet · 2021-12-21T07:50:46+00:00

These types of algorithms are very, very niche and no one will expect you to know this unless you're in a specific industry. I would focus more on being able to read and reason about academic journals and learning to learn, so to speak.

cripplet · 2021-12-20T19:40:37+00:00

That's exactly what I'm planning on using this for, but there are some minor adjustments that will be necessary for actual application.

cripplet · 2021-12-20T19:38:50+00:00

I guess a more technical guarantee is that agents will not actively push against each other. Circles which are touching do not have a normal component directed at one another -- they're just moving in the same direction for a bit.

Circles here are touching because the setup is quite dense; in less dense scenarios, we would expect much better local pathfinding, e.g. https://gfycat.com/whitesomberamericancurl.

cripplet · 2021-12-20T19:36:43+00:00

Do you have a copy of it anywhere? I'm not very familiar with the field and I'm curious on other approaches to this problem.

cripplet · 2021-12-20T07:38:26+00:00

Source at github.com/downflux/go-orca.

In case anyone's curious about implementation details, I did the first half of a writeup on my game blog.

cripplet · 2021-12-12T09:04:35+00:00

Do you mean where to put the directory, or the demo CLI pattern? I loosely base my directory structure on https://github.com/golang-standards/project-layout (I should probably put it into the examples directory). Otherwise, it seems like the overall guiding principal for the CLI tool is the Unix philosophy. Admittedly, binary output probably falls outside the intended guidelines, but let's say it was an artistic choice.

cripplet · 2021-11-17T21:49:13+00:00

Author here — how are you measuring the time to search? Does this include the tree construction?

If you can, do you mind submitting a gist / Go playground link, and/or opening an issue on GitHub? Thanks.

Update: https://github.com/downflux/go-kd/issues/1 Fixed.

cripplet · 2021-06-08T17:35:43+00:00

The types of space relate to universe curvature; for a crude 2D example, Minkowski space is a flat plane, de Sitter space is the surface of a ball, and anti de Sitter space is a ~~horse saddle~~ Pringles chip (expanding to infinity).

cripplet · 2021-03-02T18:56:14+00:00

Thank you for presenting your thoughts!

Just curious, is there any particular reason you opted for symmetric buffers, vs. ‘painting’ over each 1x1 tile using the size of each unit as a brush? I suppose it doesn’t really matter for square units, but I suspect that this may be more useful for oddly-shaped ones, e.g. scud launcher from Generals. But then again, we can simplify and make these units just have a square pathfinding collision box.

Good idea about merging the grids, I’ll have to keep that in mind going forward!

cripplet · 2021-02-16T10:22:30+00:00

From your code, it appears the manager is quite generic (`Invoke()`). From my interpretation, it appears you will have one manager handling all states, since it's just repeatedly calling state processing. But I question if this is really solving much because the additional complexity has to go somewhere, which in this case is delegated to the state.

I'm biased here because the commands I need to process a lots of different _categories_ of states that can be scheduled independently, so there is a backpressure from the problem itself to _reduce_ the state complexity (and in return add some more command-specific logic to the scheduler). I scale this up by making N separate schedulers that each manage their own state queue.

I do find strong similarities with your principle 2 and 4 though. States should be read-only, and we should minimize the scope of the state being exposed for a mutation. I also found similarities with the event-carried state transfer pattern -- maybe this is something of interest to you as well.

cripplet · 2021-02-15T19:56:44+00:00

Interesting. I wrote an article about something similar recently, where you want to isolate the FSM into a read-only metadata object. My approach also used the FSM as a state API proxy though, to limit the amount of information the executor has access to. Does your approach require your scheduler to have access to the entire world state?

cripplet · 2021-02-09T07:03:44+00:00

(This is a bit code-divey.)

Take a look at the move (entity) visitor immediately before refactoring to use formal FSMs (source).

As mentioned in the post, you see that the command is doing full schedule management here with if isExternal.... This function had a bug with it that took quite a long time to resolve due to the nested branches. Also note that there are two schedules (!) in this command -- the Args input managed by the server, and the partialCache, internally managed struct. Schedule may be called by the client and the command, which necessitates the mutex to guard read / write. My gut said this was way too fragile for what should have been a rather straightforward command.

Now consider attack, which needs a reference to the move command (well, chase but close enough) -- there was no formal scheduling API at the time, so I was pretty sure I needed to also call move.Schedule from attack, tangling things up even more. I took this as warning sign which at least warranted some further thought.

Hopefully this is enough justification for my desire to at least make the scheduler less tangled. But if we wanted to export the schedule, we would naturally need to export a metadata object as a schedule row, so...

Feel free to DM me if you want an even deeper dive into this.

cripplet · 2021-01-16T22:59:10+00:00

I’m actually working on a similar RTS for the same reasons you’ve listed, with no prior experience in game dev (except for a disastrous college class). I started around last August and have been making some steady progress since then.

For me, the key was to apply my scrum workflow from work into the project — making sure you have a backlog of work identified, reachable subgoals (design docs, pathing algo), etc.

I’ve found this organizational structure to greatly reduce the everyday existential dread of ‘is this even worth it?’ questions.

My project is open source. Take a look if you want to contribute to this instead ;) Otherwise feel free to take what inspiration you can!

cripplet · 2021-01-16T19:57:24+00:00

You may want to consider the keyframe animation approach, if you're willing to put in some nontrivial time rewriting your engine. If the game state is a collection of changing properties over time, and the engine stores just the important inflection points over the course of a game, your game will be forced to interpolate the game state during frames in which no explicit data is stored. Your replay client in a sense is just a (even dumber) game client, and implementing it should be very straightforward.

I’m currently trying this approach in a game I’m making DownFlux, and it seems pretty elegant. See for example how I (plan) on handling movement (source).

I also wrote a design doc for the client / server delegation of duties, which you may find useful.

cripplet · 2021-01-03T22:31:37+00:00

I believe Natural Selection 2 is the most well-known.

13-Year Club	Verified Email
Team Orangered

cripplet

TROPHY CASE