Print

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

[Aqizzar]

A solution so elegant even I could understand it (after re-reading)!

If I made it look elegant, I'm a better bullshitter than I thought.  It is actually almost working now, just nothing to show yet.

I was super proud of myself when, after staring blankly at a text document for three days, I scratched out a pathing map on a stickynote at work and had a node-pather in half an hour.  Except it only returned any path instead of a good path.  I may or may not have shouted myself hoarse in frustration after pouring through, no joke, about twenty different A* tutorials before finding one that was actually code-complete enough to demonstrate node-parentage.  (Interestingly, it was an iOS-Mobile tutorial.)

What's actually happening at this point: When the map generates it builds all the area-blocks and connections between them, and when an actor needs a path it actually runs an A*algorithm on the blocks themselves, which I didn't plan on.  A* is really intended for uniform fields of nodes, i.e. a grid, but it'll work on any node if you can compare them.  Then, the actor only has to path it's way through one block at a time, which I think is pretty nifty since testing the cell-by-cell pathing actually does have a split-second hang time for very long routes.

The only time long routes will have to happen is flying actors, because I discovered my block-parsing code takes a 10-20 seconds to analyze all open space on a map.  Originally I was going to have all open space be rendered as area-blocks as well, but it's completely pointless so I won't.  Parsing all space you can platform on takes a second at most, so that's awesome.

The only reason any of that matters is because the pathing map has to be recalculated every time a cell on the map changes.  I can limit this by only recalculating nearby blocks instead of the whole map, but I'm already looking down the road at problems like jumping-paths having to be recalculated because you never know what path is going to be intersected by what block until you look.

Holy crap that is a lot of obtuse rambling.  I need to get back to work so I can show what I'm talking about.

[Kyzrati]

Looking good Aqizzar! Been silently stalking observing your progress since last year, and this is quite an interesting project. Hopefully you take it through to playability!

I did miss your post from a week ago about pathfinding, but it seems you've come up with a nice solution on your own already. A* isn't really "meant to" be used on uniform space, it just happens to be that most of the examples you might find on the web, and basic tutorials etc., tend to work that way for simplicity. A* just operates on nodes, which can be anything at all (that's why it even works for cool things like GOAP). Did you discover this on your own?! Pre-calculating goes a long way towards speeding everything up (especially in the complex environment you've got here), but developers who work with dynamic environments have our work cut out for us due to the need to update/recalculate as necessary...

Reminds me of X@COM, which is a standard grid-based 3D world, but the node map includes "teleporter" nodes which can be attached to another "teleporter" in a map; while I've never actually used teleporters in that game yet, when they do exist the AI will naturally path through teleporters if it will get them somewhere quicker, because stepping through one to another point on the map is just another move. Finding the "best" path is just a case of making sure each node is checking the specific "cost" of reaching it from whichever direction the path came from.

And while not many people use C# for roguelikes, I believe that's because many RL devs are beginners who'd prefer to work with something like Python, go with something very portable like Java, or experiment with weird alternative language choices, not tap into the raw power that is C#! I say good choice. What IDE do you use?

[Aqizzar]

A* just operates on nodes, which can be anything at all (that's why it even works for cool things like GOAP). Did you discover this on your own?! Pre-calculating goes a long way towards speeding everything up...

That was the idea, yeah.  I might have had some distant inspiration on the precalculated map thing from Wolfenstein 3D of all games.  In that, actors would move toward you if they were in the same room, but it also used the rooms as a sound map.  If there was an open door, any sound you made could be heard in that adjacent room, and actors would path towards the door because they couldn't reliably path around the walls.

But really, this precalculation idea came to me as the only viable option.  Having every actor do a proper sweep of the map every time they wanted to move would have been too much processing.  And I felt like it would be a good project when I had the idea.

...the AI will naturally path through teleporters if it will get them somewhere quicker, because stepping through one to another point on the map is just another move.

Funny you'd mention that, I was just thinking about teleporters.  And how they might reveal a critical weakness in my movement process.

I haven't worked out the cost function of movement, but I'm not sure I'll really need to.  My engine doesn't have a concept of "speed" so all actions cycle at the rate of input (the player cycles one action, everything else processes one cycle, etc.).  Functionally, there's only three types of movement in this engine: walking, falling, and flying.  Jumping is just a kind of falling, after all.  The pathing system considers every action equal.  Walking onto a ladder from a platform costs the same movement (one turn for one cell) as jumping (one turn for a few cells), and 99% of the time jumping/falling will be faster anyway so it all works out.

I do foresee some issues like making sure actors don't take falling paths that will kill them, and making sure the precalculator doesn't draw a million jumping paths so actors bunnyhop everywhere (at least making sure transitions never connect to the same block).  Right now my biggest concern is getting actors to reliably understand what block they're in (especially if blocks overlap), and recognizing whether or not a movement was successful (since deciding what to do and actually doing it are separate processes).

What IDE do you use?

Visual Studio 2010.  I used to use SharpDevelop, but I have a real job with C# now so I just use the same tools I have at the office (or the free versions anyway).

[Kyzrati]

Funny you'd mention that, I was just thinking about teleporters.  And how they might reveal a critical weakness in my movement process.

I haven't worked out the cost function of movement, but I'm not sure I'll really need to.  My engine doesn't have a concept of "speed" so all actions cycle at the rate of input (the player cycles one action, everything else processes one cycle, etc.).  Functionally, there's only three types of movement in this engine: walking, falling, and flying.  Jumping is just a kind of falling, after all.  The pathing system considers every action equal.  Walking onto a ladder from a platform costs the same movement (one turn for one cell) as jumping (one turn for a few cells), and 99% of the time jumping/falling will be faster anyway so it all works out.

I do foresee some issues like making sure actors don't take falling paths that will kill them, and making sure the precalculator doesn't draw a million jumping paths so actors bunnyhop everywhere (at least making sure transitions never connect to the same block).  Right now my biggest concern is getting actors to reliably understand what block they're in (especially if blocks overlap), and recognizing whether or not a movement was successful (since deciding what to do and actually doing it are separate processes).

Ah, so the movement cost is essentially uniform. That was somewhat unexpected, as you'd think climbing would take longer than falling, unless I've misinterpreted your concept. Either way, the idea of "costs" could still come into play to solve questions like which way an AI *prefers* to go. For example one particular route may be more dangerous (a chance of falling?), or they're trying to avoid something. Not sure at this point what possibilities might occur in your game. Of course, in some cases it can also be nice to design around these issues for practical or technical reasons.

[Aqizzar]

Total coder boner.  That represents several hours of work going from theory to practice, since there's so many different special cases and odd considerations.  Mainly making sure the actor didn't path to the same block twice without excluding all connections from the starting block, and keeping the actor from getting to an overlap and pathing to the same cell forever.  Amazing how well it works when ironed out, and with no noticeable processing time to boot.

Of course, the actor is spawned and set in motion by a couple buttons, the pathing map has to be updated manually, there's no falling or jumping yet, and I kinda forgot to account for not finding any path.  But hey, details.

I'm not sure why I made the actor the same color as the constructions.  Hopefully natives to this forum as ASCII fluent enough to figure out what's going on.

Ah, so the movement cost is essentially uniform. That was somewhat unexpected, as you'd think climbing would take longer than falling, unless I've misinterpreted your concept.

I may not have explained that right.  A ladder is a "block" just like a platform is, the transition between them is the one cell where they overlap and the actor moves from one to the other.  A falling transition is just the one step out into open space to let gravity take over.  So when moving from a level to another level by either a ladder or falling, the ladder has an effective cost of its height in cells, while falling always has an effective cost of one cell.  That's a good candidate for a more elaborate evaluation, especially when falling damage comes into play.

[MaximumZero]

Very nice, ser. Very, very nice.

[Kyzrati]

Looking nice! Hold on to that feeling of elation as long as you can, because dealing with all those "details" sometimes turns out to be the soul-sapping hair-pulling part

I may not have explained that right.  A ladder is a "block" just like a platform is, the transition between them is the one cell where they overlap and the actor moves from one to the other.  A falling transition is just the one step out into open space to let gravity take over.  So when moving from a level to another level by either a ladder or falling, the ladder has an effective cost of its height in cells, while falling always has an effective cost of one cell.  That's a good candidate for a more elaborate evaluation, especially when falling damage comes into play.

So regardless of how high you fall from the game only advances by 1 turn?

[Aqizzar]

Looking nice! Hold on to that feeling of elation as long as you can, because dealing with all those "details" sometimes turns out to be the soul-sapping hair-pulling part

Don't I know it.  I'm looking at two major tasks next: Jumping, and auto-adjusting the path map when a cell changes.  In the case of jumping, I'm actually just going to use static templates of jumps made at different velocities which the program will use to see if one block can be reached from another.  The map adjusting is... Well it sounds simple in theory, I'm just not sure how many parts of my first-cut pathing intelligence will be broken if the map changes during travel.  I tried to engineer it with this in mind - actors do draw a full path to their destination, but they only 'commit' to moving to the next transition point, then recalculate their path to make sure it's still good.  I'll soon know just how visionary I really am.

So regardless of how high you fall from the game only advances by 1 turn?

No no no, see, initiating the fall only takes one turn, falling is still ruled by gravity and acceleration.  The actor only considers that it has to step out into space, it doesn't know how many cycles the fall will take to complete.  I could probably do that, but I figured it'd be fine as is, since there's almost never going to be a situation where climbing down a ladder cell-by-cell would be faster than falling/jumping.  I will have to make the actor compare the length of a jump/fall at some point, to decide if it actually wants to fall that far, but it doesn't really need to know how many cycles that would be, since falling more than three cycles would clear over a dozen cells anyway.

[Kyzrati]

No no no, see, initiating the fall only takes one turn, falling is still ruled by gravity and acceleration.  The actor only considers that it has to step out into space, it doesn't know how many cycles the fall will take to complete.  I could probably do that, but I figured it'd be fine as is, since there's almost never going to be a situation where climbing down a ladder cell-by-cell would be faster than falling/jumping.  I will have to make the actor compare the length of a jump/fall at some point, to decide if it actually wants to fall that far, but it doesn't really need to know how many cycles that would be, since falling more than three cycles would clear over a dozen cells anyway.

Ah, I get it now. Seems like this method will hold up in most situations given the world as it exists now.

Your jumping solution sounds like it should work, too. In theory ;p
See you (or your '@') on the other side.

[winner]

I confess I don't entirely understand why you didn't use djikstra's path finding algorithm (A* without the estimate of remaining travel distance).
It works on any direct or undirected graph with variable movement costs. The performance is fine for graphs of this size (I had dozens of critters recalculating their paths every turn with no noticeable delay.)

[Aqizzar]

I confess I don't entirely understand why you didn't use djikstra's path finding algorithm (A* without the estimate of remaining travel distance).
It works on any direct or undirected graph with variable movement costs. The performance is fine for graphs of this size (I had dozens of critters recalculating their paths every turn with no noticeable delay.)

I didn't think at all about Djikstra's because a name like A* is way easier to remember.  They both ultimately return a least-cost path, and A* does a bit less cascading calculation in a lot of cases.  Besides, most of the actual cell-by-cell pathing will be taking place in extremely narrow areas (usually one-dimensional paths) so implementing any particular algorithm was about convenience.  Pathing through an abstract grid like my block-connection structure I think makes A* and Djikstra functionally the same, since it really just uses the distance-estimate to sort which cell it looks at first.

Anyway I'll stop shooting my mouth off.  Next game plan:

Finish implementing dropping and jumping paths.
Update the blocks and connections near any cell that changes as efficiently as possible.
Give actors some way to set their own pathing goals.
Give the player a way to assign actors into groups, who then try to stay relatively near each other.
Give the player a way to set waypoints and landmarks.
Assign AIs to travel from one spot to another on command.

I keep feeling like I've reached a point where features fall into place faster than I expect them to.

[Aqizzar]

Been a few days, figured I have something to chat about.

Finish implementing dropping and jumping paths.
Update the blocks and connections near any cell that changes as efficiently as possible.

Second one worked way better than I thought it would thanks to good planning.  First is proving difficult.  Actors will jump from block to block (because they don't really do any thinking on their own), but getting the pre-plotter to recognize proper jumps has me chasing my tail.  Along with a noticeable lag time in jump calculations that I think I can clean up.  So, still in progress.

After that practical problem, Groups are turning out to be a weird theoretical problem.  When you think about it, a Group is a thing that needs to exist within a single area and be able to move around the map with the same rules as the Group's members, but it's not really an "object" in itself.

I find myself stealing a lot of ideas from Dwarf Fortress in deciding how Groups should work.  Namely that a group always has to have at least one member, a Group has an anchor point that members try to move to and orbit around, and the Group is the bottom of a three-level organization structure.  About that last part: All actors in the game world will be part of three layers of association, basically the same way Dwarf Fortress works.  I don't really consider this ripping anything off, because it's a perfectly natural structure.  The layers are (names kinda pending) Alignment, Company, and Team.

Alignment is like an Entity in Dwarf Fortress, all the actors that basically share an overall directive and list of relationships toward other Alignments. 

Company is like the population of a specific Fortress, except that a Company isn't necessarily tied to one place.  This is were production orders, facilities, and most inventory is handled.

And then Team is like a military squad, told to do specific actions like "mine this" and "patrol there", with uniform equipment and schedules.  Each Company has a background Team for all the members not assigned to a specific one, which do the tasks assigned to the Company.

The difference between this and Dwarf Fortress, among many many others, is that the Player controls things from the top level instead of just the middle level, in addition to being a character running around in the world that Teams can be ordered to assist.  Not to make too much of a comparison, y'know, that's just the idea.

For obvious reasons, I'm just worrying about the Team level grouping for now, and really want to get jumping done first.

[Aqizzar]

Surprisingly, I only pulled out most my hair getting this to work.  A majority of the speedbumps were "similar variable name" related.



Sending an actor on a little round trip.  They don't always choose the most efficient path, like I have no idea why it decided to jump to that second platform before getting on the ladder, although I'm not entirely sure it didn't grab the ladder mid-flight.  Since I didn't code that to be a thing that can happen I'll probably dive into it at some point, along with working on the path valuations since that wasn't even the quickest route.

Later.  I've had about all I can stomach from my pathfinding engine for a while.  I might do a little performance work, but otherwise I'm on to Grouping now.  Oh boy.

[Aqizzar]

So, you might be wondering whole ol' Aq has been doing for the past ten days.  Aside from doing more planning than coding, I've also been teaching myself about the dark arts of Application Threading.  In other words, I now know how to make programs that run in real time.  (And to think I spent no dollars on Game Maker, oh ho ho.)  I was actually inspired to check threading out by an idea for a Seven Day Roguelike I had and planned to do this week, but like most of my ideas it sounds like a giant pile of work.

But what does that mean for this project?  Well, a lot actually.  I love me some roguelikes to be sure, but it's not really what I want to do.  As if making a platformer wasn't proof enough.  I really really want to use my newfound and still very flimsy knowledge for something, but I'm left with a big decision with three options:

One, I continue making Lunkheads Zero as it is now, and work on a separate real-time game.  I have never once succeeded at maintaining simultaneous projects.  Ever.

Two, I scrap my Lunkheads Zero concept and make some completely new thing, perhaps revisiting my dream game someday down the road.

Three, I gather up everything I've learned and transform Lunkheads Zero into a real-time side-scrolling platforming roguelike.  Or in other words, a traditional platformer presented in ASCII.  Which will probably only last as long as it takes for me to learn how to display gridless graphics on my own, then I won't need Libtcod to do the hard work and I'll basically be making the Terraria-knockoff I always envisioned.

Obviously number three is the smart answer (although I do have a side concept or two I'd love to take a crack at).  It is not a simple task by any means, although I think I was smart enough to give myself a head start.  Most of Lunkhead's internals process almost asynchronously to the player's input, and I knew from the start to make actions and actor intelligence separate processes.  The biggest challenge will be rewriting the physics engine to process in "real time" i.e. as often as a thread calls it, namely because it has to produce believable motion in a grid-based environment without choking on weird fractional cases.

I'm honestly kinda overwhelmed by the idea, although I already know it's the only option I can accept.  I did plan to try to make something for 7DRL, so Lunkheads might not see any progress for some time.  But... Yeah.  That's what Aq's been doing.

[Kyzrati]

Since you're just doing it as a hobby with no absolute goal in mind that you have to reach, I say do whatever you feel like doing now. This assumes you're in it for the pure fun of doing interesting things. Now if you hope to one day "finish" something on the other hand, then repeatedly changing directions is a bad idea. But then, you started with a rather big project to begin with, so maybe in the back of your mind you already knew where that was headed...

Try a smaller project with your newfound tech!