Generated Graph optimized A* Pathfinding

WIP games, tools & toy projects
#1


Pathfinding Demo
Lighting Demo
JAR: http://www.java-gaming.org/user-generated-content/members/244457/monster-12-23-17-3.jar

  • please leave feedback :slight_smile:

Technical description:
The demo’s purpose is to showcase how to use A* pathfinding when the moving-agents are not constrained to move rook-like (horizontal/vertical only). If we were to go with the simplest solution, i.e. creating a graph with all moveable map locations as nodes, and all nodes with direct line of sight of each other as connecting edges, then we would have much worse performance. Instead, we filter the graph nodes, only adding those nodes that are “important,” e.g. could possible be a “turning point” in any path found. These “important” nodes are the cyan colored squares in the demo, and, as you can see, they are much much sparse than the collection of all the map’s moveable locations. With the map sizes of the demo (50 x 50), the maps have 2500 total spaces, of which ~400-600 are moveable; while the generated graph only has ~30-80 nodes. I.e., we’re filtering out ~88-92% of all possible nodes, which results in an even more drastically reduced number of edges our generated graph will have.

1009×1031 505 KB

Game description:
I’m in early stages of working on a asynch human v.s. monster game.
Both characters are inside a dark house, and the human has to find the exit before the monster finds the human.
Running makes you louder.
The human has a light which, when turned on, allows him to see further, but risks revealing his location if the monster has line of sight of the lighted areas.
The monster, on the other hand, can fully see in the dark, but the human can only see near itself when his light is off.
The monster is slightly faster so the human can’t outrun the monster; but the monster is slightly louder, so the human can hear the monster’s noise without being heard himself.

That’s the basic idea. It’s really early in development, so there aren’t any useful screenshots or videos of the game to showcase. But instead, I made this demo app to showcase the house generation and pathfinding. As the game is in java, I made this demo originally in java as well, so it would be easier to integrate later. But, for the purposes of this showcase, I made a javascript version hosted online so you wouldn’t have to download a jar just to play around with the quick demo. I can provide the java version as well if someone wants it.

https://path-finding-graph-generation.herokuapp.com/
https://github.com/mahhov/pathfindingGraphGeneration (includes animated gifs)

Note, the house generation isn’t perfect (isolated rooms are removed, but isolated sets of room are not), but that’s just a minor issue that I’ll fix when the time comes.

Feedback greatly appreciated :slight_smile:

#2

Here’s a little gif showcasing the pathfinding algorithm in a random-wanderer character (picks random destination anywhere on map, and moves towards it; upon reaching the destination, repeats). Currently, there’s that small snagging it has on corners, but I’ll fix that.

#3

I’ve actually tried out this exact pathfinding system myself. It’s REALLY nice and clean and is a LOT faster for stuff like long corridors. It pretty much generates completely optimal paths in contrast with a grid-based pathfinder. However, it really can’t handle open spaces well, as you end up with all corners connecting to all other corners over extreme distances. These checks are expensive and slow. In my case I needed to be able to modify the terrain efficiently and there was a very big risk of large open rooms with massive amounts of edges, so I ended up dropping it.

#4

Hmm… Regardless of the size of room, given it’s rectangular, it will only have 1 node per entrance/exit. This algorithm is actually meant exactly for these kind of situations (rectangular areas, few corners / bends / curves). Room corners should not have nodes, as they can’t possible be part of any path unless the path either begins or ends at the corner (they’re like dead ends). Maybe your rooms weren’t rectangular? or we’re using slightly different algorithms?

See below, there are 3 rooms and 2 hallways connecting them. The only nodes we need are the 4 for the hallway exit/entrance plus 2 for the start and end of the path.

One thing I noticed while trying this out, as the algorithm doesn’t have a notion of “inside” versus “outside”, i.e., it doesn’t realize the areas outside the rooms are not walkable, even though they’re empty, you can end up with nodes generated in the “outside” areas that are useless. To avoid this, we can either 1) add flood-fill checking step to the algorithm to ignore areas that aren’t connectable to path start/end. 2) or we can fill the outside areas of the map so the algorithm knows they’re not walkable. 3) Or (this is my approach), we ignore this problem all-together, since the graph is only generated once, and then reused, so this is just a few ms startup delay, rather than something that slows down the game loop.

#5

My open areas were not rectangular, but organic. Try a big diamond-shaped room and then let my grand children know the results. :wink:

#6

Cool stuff, I like your GIF’s, they show the approach really well.

That’s a really good game idea too, how will you represent sound? Graphically or just through the speakers? Would be cool if the sound waves were visible and diffracted around walls.

I tried something similar here:


Some screenshots are here (but the webstart and applet no longer work, I’ve been meaning to clean it up):
https://code.google.com/archive/p/straightedge

One thing I noticed is that the ‘player’ square sometimes gets stuck on the corners. I found that by ‘buffering’ the obstacles by the width of the player (making the obstacles bigger so the nodes are further from the obstacle edges), then the paths would accommodate the width of the player better. JTS is great for buffering polygons:
http://www.tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/geom/Geometry.html#buffer(double)

[quote]I’ve actually tried out this exact pathfinding system myself. It’s REALLY nice and clean and is a LOT faster for stuff like long corridors. It pretty much generates completely optimal paths in contrast with a grid-based pathfinder. However, it really can’t handle open spaces well, as you end up with all corners connecting to all other corners over extreme distances. These checks are expensive and slow. In my case I needed to be able to modify the terrain efficiently and there was a very big risk of large open rooms with massive amounts of edges, so I ended up dropping it.
[/quote]
I found a similar problem, so I put a limit on the maximum distance to join nodes. I found that open rooms could be sped up by ordering the obstacles from closest to furthest, so the lines between nodes can be checked for intersections against the obstacles most likely to get in the way. This provided a big boost in speed.

That’s interesting about modifying terrain on the fly. I cached all fixed obstacle intersections at the very start before the game began since I also found that took a long time.

One thing that @Riven mentioned a long time ago which would be interesting, is to use ‘natural pathfinding’ by limiting the nodes to what is visible. This would probably involve a trial-and-error approach.

@Jono is very knowledgeable on this topic, he’s actually taught A* and other algorithms in class. He provided some good tips for me here:

#7

Here’s the fix I promised for the getting stuck on corners. The issue was just too large of an epsilon (I was using 1) when trying to determine when to turn the corner. So basically, when the character reached within 1 unit of the node, it would move on to the next corner, but that was way too large, I’m using 0.1 now.

@theagentd, yes non-vertical/horizontal walls in a grid-system would produce a lot of nodes with this algorithm. I wonder if we added the notion of major and minor nodes, where a nodes, where major are the one’s diagonal from walls, and minor nodes are the one’s both diagonal and adjacent from walls; then for pathfinding we use only major nodes for pathfinding, unless we get stuck. I think this might work, since an optimal path would not be dipping into the cracks of the diagonal walls.

@CommanderKeith, that is very helpful, my next steps are to add a lightning system. Such as the characters can only see the parts they have line of sight for; the human can only see x units with light turned off, and y units with light turned on; the monster can see in dark just fine; but if the human turns on light, then the monster may see the light cast by the human. I’ll definitely take a look at those posts to see what kind of optimizations I can do for this lighting system.

#8

Got a simple lighting demo up and running, now need to integrate with the main java app.

961×977 244 KB

961×977 1.29 MB

#9

And I’m still lurking here! Not a lot to add though as this all looks pretty slick to me.

I’ve implemented a similar style of map pathing between entrance/exit nodes of map areas taken from a fixed set (this would be analogous to having a fixed set of room layouts in these maps). The areas had additional static obstacles inside them and I pregenerated flow fields towards each exit for every room. The flow fields might work around movement problems with non-rectangular rooms too I suppose.

#10

Hmm… precomputed flow maps seem like they would only work with static endpoints, as they would be function of the destination/exit endpoint. I wonder what your use case was, why would a map have multiple static entrances / exits, but not a precomputed path to follow?

As for lighting, my next problem to solve is how to compute color based on lighting.
Currently, I’m using some function of distance between light source and light destination to compute light intensity for that destination. Then I use that light intensity to multiply the destinations color. I.e., given distance d (d>0), I compute light intensity L (0<L<1). Then, assuming, under ‘pure’ light, color(r,g,b), I paint the area color(rL,gL,b*L).

The question is what function to use for determining light intensity based on distance. According to wiki, light intensity is inversely proportional to square distance, but 1) this becomes too dark too quick, and 2) the technical light intensity wiki and physics refer to probably isn’t the same as what I’m referring to L.
I’ve tried stuff like 1 - constant * distance, as well as 1 - sqrt(distance), both seem to be ‘ok,’ but I’m wondering if anyone has experience what function seems to work best.

637×669 241 KB

If anyone wants to try out different lighting functions and see which one they like, please feel free

Lighting Demo

#11

Mixing Linear and Quadratic Falloff could produce some nice results:
https://developer.valvesoftware.com/wiki/Constant-Linear-Quadratic_Falloff

Or you could try using one of those online curve fitting tools to fit a function to some measured falloff curves like this one for example:

#12

Interesting ideas with the formulas and curve fitting. I just used Java2d’s radial gradient paint with the radius set to the maximum bounds of the vision field

#13

This was for fairly complex areas and the flow maps also solved the beginning and ending of the paths. Pre-computed paths should do much the same thing.

In my case it was actually hexagonal tiles with no corridors. The shared entrance/exits were the 12 points at vertices and centre of each edge of the tiles.

#14

I decided to go with the 1 - distance / maxDistance lighting function. It seemed to look the nicest plus it’s easy to set it to the required max distance.

Next steps:

  1. multiple light sources randomly spread throughout the house. They will flicker or turn off as the monster approaches to add a sense of gloom and provide the human a way to know he’s really close to danger and in what direction the monster is.
  2. win conditions. If the human reaches the exit, he wins, but if the monster reaches the human first, the human loses.
  3. sensory information. The human should be able to hear (probably some visual indicator as well) when the monster is close. The monster should be able to hear/smell the human. Probably, the human will sense farther than the monster so that it can avoid the monster, but the monster will be able to determine the human’s exact location, whereas the human only knows how close he is to the monster. Running should make the human/monster move faster but also audible from farther away. Maybe the human has some kind of re-chargeable / cooldown-limited pulse equipment that will tell him the monsters’ (approximate?) location.

#15

Light falloff values are VERY dependent on you doing correct gamma correction. If you just output linear 8-bit color values without any modification, your monitor will essentially run those through approximately x^2.2. I may be mistaken, but the fact that you think a linear falloff looks the best seems to indicate that you’re not doing gamma correction.

A lack of gamma correction is especially noticeable when adding together light values. If you write out 0.2 as your light value, that gets mashed to 0.2^2.2 = ~0.029. However, if you have two lights that add up, both with the same intensity, you get 0.2+0.2=0.4 —> 0.4^2.2 = ~0.133. In other words, adding together two lights makes the result over 3x as bright, not 2x.

It is imperative that you get gamma correction working before you start tweaking things like this.

#16

You’re totally right, I’d never heard of gamma correction prior to ur comment, and was not accounting for it. Quick wiki + stackoverflow search suggest something like [r*|g*|b*] = 255 * ([r|g|b] / 255) ^ (1 / 2.2) might be all i need, I’ll try it out sometime and see what happens.

In the meantime, I implemented multiple light sources. To be honest, I don’t like it. Below is a gify if anyone wants to share their opinion, but I felt like it didn’t fit with the top down view. It provides the the human with sight of rooms that he doesn’t have line of sight of and therefore killing the “spooky” feel. if I were restrain it to only being visible when the human has line of sight of the lighted areas, then it’s pretty pointless as the human’s light source would’ve lighted the area anyways.

#17

Yeah but you can then have dim lights of different colours here and there which can look nice. Eg. fireplaces, lava pools, mysterious glowing pond, etc.

Cas :slight_smile:

#18

Awesome idea, would be nice ambiance setting the mood. Especially if they flickered or turned off as u approached them or such. Art and visual polish have always been my weakness in my projects, not sure if i’ll pull it off as nicely as u described, but will give it a shot.

In the meantime, i’ve worked on the victory conditions (human wins if he encounters the exit, and loses if he encounters the monster) and the sensory information. The sensory information might require adjusting, but for now, the human has a red bar indicate his distance from the monster if they’re 12 units or closer. The monster senses and chases the human if they’re 9 units or closer.

Feel free to give it a try and let me know how it feels :slight_smile:

JAR: http://www.java-gaming.org/user-generated-content/members/244457/monster-12-18-17.jar (see top post for most up to date jar)

(stupid question maybe, but does anyone have experience with “java web start”? Would it allow me to host my project on a website for u guys to demo without requiring downloading the jar?)

#19

[quote]java web start
[/quote]
Eww, NOPE you better get something like LibGDXs gwt/javascript/html export thingy going, web start is pure cancer, you will lose your players before they even started the game.

[quote]how it feels
[/quote]
The movement and lighting feels ok.
There is a minor bug with moving along walls, you are slower when you slide against a wall with for example “W+D” pressed vs only “W”.

The “game over” gets triggered before the Monster fully touches you, which pisses me off, especially since you cannot see very far.
The monster is way to fast and the environment is way to tight and wrinkly for running away effectively, you basically can’t beat the monster without exploiting bugs or pure luck if at all.

The random map generator sometimes does not connect the players room-structure to the room-structure with the monster in it :smiley:

The gameplay feels bad, my experience was running around aimlessly and then getting the monster flung at my head at lightspeed and BOOM dead.
Also there is no restart button, so you have to exit and re-launch the application for a new round.

Definitely needs some tweaking.

#20

@VaTTeRGeR Thank you so much, that was a very helpful :). I agree completely with your feedback, and will be sure to improve the project.

Regarding the movement, I thought this feels more naturally, as your running into the wall it makes to lose speed. But I wasn’t sure since the tight corridors makes it easy to slide into walls as your’e trying to turn a corner. Your comment convinced me :), I’ll fix it soon.

Regarding game over before monster touches you, you are right, i set the victory condition distance arbitrarily as 2 units, but I’ll change it to something more reasonable, like 0.5 or such, after I test it out.

Regarding the monster speed, it’s 50% faster than the human currently. I’ll try speeding up the human, slowing down the monster, increasing the light range, or increasing the human sense distance (red bar when you get near the monster), and see what values work well. (Side note, if you press ‘.’ you run twice as fast as the monster but you’re not supposed to know about that since running isn’t fully implemented :)).

I’m aware of the bug with the map generator, but just haven’t gotten to it yet. It basically removes all rooms that are totally unconnected to other rooms, but doesn’t do the required search to determine if all the rooms remaining are connected.

I’ll definitely add a restart button or maybe text “Press Enter to Try Again” or such. It’s even annoying for me when debugging to have to restart :).

All that being said, you pointed out two of the most significant issues I’m having, 1) better map generation to avoid the “tight and wrinkly” repetitive maps, and 2) some kind of clues as to where the exit is or some way of figuring it out without relying on pure random luck and walking “my experience was running around aimlessly”