Bay 12 Games Forum

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).

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.

I forgot which language this is in... I was going to say if it's C++ use pair instead of tuple, but then realized C++ doesn't have a Dictionary class.

C# actually, which I think is the least popular of all languages to write roguelikes.  The frontend display plugin I use, Libtcod, has so little discussion or documentation on the C# version that this forum is the third or fourth Google result.  There are probably simpler things I could use besides Tuples, but I just found them and thought it'd be cool.

---

Let's talk about pathfinding.

In a typical, that is top-down, roguelike or almost any planar game where you don't have to worry about things like gravity, pathfinding is pretty simple.  Just do an A* floodfill from Point A to Point B, or any of the performance improved alternatives if you'll accept an uglier path.  This can become a noticeable problem with realtime games but not really anything made in the last 15 years unless you've got a huge number of calculations hitting a very complicated space.

Performance is not my worry, even though I do want to make a real-time game eventually.  My problem is that A* fills are kinda useless for a platforming game, because the rules of movement are all different.  With a top-down map, you only have to consider whether or not you want to walk on a particular coordinate.  For me, consider a map like this:



Nomenclature: The ladder looking things are ladders, the thin platform looking things are platforms you can walk on or choose to drop through.  I know this is complicated side-scroller stuff, try to keep up.

In this scenario, Point A can walk to Point B and vice versa, but getting from A to B is a lot faster if you're allowed to drop off a ledge.  Getting from Point C to D also requires this, and it may or may not be possible for Point D to reach C depending on whether and how far D can jump.  Point E has two major paths to reach Point D, but has to consider how far it wants to fall.  And any part of this map can change due to the voxelized nature of the game.

I don't actually know how games with height mechanics do their pathfinding.  You can look at games like Terraria or Starbound or 3D games like any Bethesda title and easily the confuse an AI trying to reach you.  Stand on an unclimbable object and watch them dance and bounce below your feet.  I suspect that most games take the easy route of just having the AI consider getting closer with the X-axis and leave the Z-axis to semi-random jumping.  I can't recall any platformer-AI that can double-back and path around obstacles.

These are by no means difficult problems.  There's an annual competition to write Java programs that can play Super Mario World in ways a human would never conceive, although teaching an AI to follow pathing goals more complicated than "go right" does raise the bar a bit.  I don't know exactly how these guys do their thing and while I'm curious, I've got something completely different in mind.  And I think it'll prove useful with an engine that has to consider pathing in real-time.  Behold (disco warning):



When the map generates, it group up every coordinate, and compares it to the coordinates around it.  In then makes a list of "blocks" composed of contiguous cells with the same movement type; in this case, tiles you can walk on, tiles you can climb, and tiles you can drop from.  Then it cycles through all the blocks to consider every other block: What blocks does this overlap with?  What blocks can be dropped to?  What blocks can be reached with different lengths of jumping?  All of this information is stored as static Connections.  With this precalculated map, when an actor has to get from Point A to Point B it doesn't have to consider every cell between the two all the time:

I am currently in Block 3, where is my target?
Target is in Block 5, does Block 3 overlap with Block 5?
No, what blocks does Block 3 connect to that can reach Block 5?
Do I have the movement types needed to cross those Connections?
How many cells will each path take me?

And so on.  That way, each AI is only flood-filling a small one-dimension-ish portion of the map at a time.  This also means that whenever a tile in the map changed, only a small portion of the map has to be updated.  The player could certainly spoof this with a bunch of adjacent ladders or weird jumping windows, but it's an idea I'd like to pursue.

So, that's what I'm working on now.  If nobody hears from me in a while, send help, I'll probably be very hungry.

So, State of the Union: What you guys think (of the one or two who watched it)?

It was a bit more combative than I honestly expected, but when you're going into your last mid-term election you need come out swinging.  He certainly made no bones about defending the health care program or his federal minimum-wage increase, and about as personally-directed as a President is allowed to be in a speech.  Also fascinating seeing him denounce his own party for trying to pass sanctions on Iran without his approval.

I found it far more interesting that there are now five different Opposition Responses.  The official Republican Party one, the slightly different Spanish translation, the official Tea Party response, the official Rand Paul Party response, and the official Ted Cruz pre-response because he's apparently a time-traveler with a spotty memory.

Apparently my google powers surpass even Janet.

Fear me mortals. I am become google searcher. Finder of... Words?

I think we used to call high-master googlers Disciples of Footkerchief, but he doesn't make himself known as often now.

Also, thanks again!

RAADS-R:
Total score: 83.0
Language: 5.0
Social relatedness: 38.0
Sensory/motor: 19.0
Circumscribed interests: 21.0

I have no idea what any of these numbers mean, the results graphs feel really contradictory... Wait, is that part of the test?

Although I seem to fit the "neurotypical" pattern to a T.

Quote from: Aqizzar on January 21, 2014, 10:12:46 pm

Quote from: wierd on January 21, 2014, 10:09:03 pm

You can't have a 3rd option, and still use a boolean.

True, false, and null.  Which would be... kinda appropriate, provided your table design allows it.

Actually that is very language specific. Nullable booleans are a feature of more higher level languages typical these days, but there was a point in the past where they didn't real. Your boolean is actually a pointer to a boolean, and that boolean may only be true of false, but the pointer may be null.

Actually, I was referring specifically to the database concept, since a database entry is essentially a pointer.  In any version of SQL going back to at least the early 90s, you could define a boolean field as nullable which still allocates memory for the value, but just doesn't store anything there except the null itself.  A boolean might be a single byte in programming terms, but for any data storage system that's existed since the days of physical switches a boolean consists of both the byte and the address.

Just for clarity of course.

And I looked into my job's database today.  Turns out we store gender on multiple tables, in some cases as a male/female boolean, in others as a single character, in others as a six-character string.  If there is one programming sin greater than poor extensibility, it's inconsistent standards.

Meanwhile, I came across this:

 http://qntm.org/gay

Who knew that gay database design made a lot more sense than feminist programming languages?

As a database designer myself, this is an article after my own heart.  Also, anyone working with a SQL-style database who doesn't understand the power of cross-reference meta-tables deserves to be taken out in the street and shot...

Speaking of which, I'm pretty sure the database template my company uses for personal information stores gender as a boolean.  I don't remember which value counts as "true".