Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (748)
Games in Android Showcase (226)
games submitted by our members
Games in WIP (834)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Generated Graph optimized A* Pathfinding  (Read 3601 times)
0 Members and 1 Guest are viewing this topic.
Offline buddyBro
« Posted 2017-12-09 19:01:38 »


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

- please leave feedback Smiley

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.

Click to Play


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 Smiley
Offline buddyBro
« Reply #1 - Posted 2017-12-13 16:17:47 »

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.

Click to Play

Offline theagentd
« Reply #2 - Posted 2017-12-13 16:59:45 »

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.

Myomyomyo.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline buddyBro
« Reply #3 - Posted 2017-12-13 17:10:31 »

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.

Offline theagentd
« Reply #4 - Posted 2017-12-13 17:22:58 »

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

Myomyomyo.
Offline CommanderKeith
« Reply #5 - Posted 2017-12-14 00:03:34 »

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:
http://www.java-gaming.org/topics/straightedge-2d-path-finding-and-lighting/23427/msg/196777/view.html#msg196777
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%28double%29

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.

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:
http://www.java-gaming.org/topics/a-pathfinding-through-2d-polygons/19539/msg/156371/view.html#msg156371

Offline buddyBro
« Reply #6 - Posted 2017-12-14 22:29:04 »

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.

Click to Play


@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.
Offline buddyBro
« Reply #7 - Posted 2017-12-15 18:12:40 »

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

Click to Play


Click to Play
Offline Jono
« Reply #8 - Posted 2017-12-15 21:11:03 »

@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:
http://www.java-gaming.org/topics/a-pathfinding-through-2d-polygons/19539/msg/156371/view.html#msg156371
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.
Offline buddyBro
« Reply #9 - Posted 2017-12-15 22:28:21 »

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(r*L,g*L,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.

Click to Play


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

Lighting Demo
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline VaTTeRGeR
« Reply #10 - Posted 2017-12-16 00:36: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:
Offline CommanderKeith
« Reply #11 - Posted 2017-12-16 05:50:40 »

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

Offline Jono
« Reply #12 - Posted 2017-12-16 07:37:40 »

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?
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.
Offline buddyBro
« Reply #13 - Posted 2017-12-16 17:31:44 »

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.

Click to Play

Offline theagentd
« Reply #14 - Posted 2017-12-18 13:26:37 »

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.

Myomyomyo.
Offline buddyBro
« Reply #15 - Posted 2017-12-18 15:13:41 »

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.

Click to Play
Offline princec

« JGO Spiffy Duke »


Medals: 993
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #16 - Posted 2017-12-18 15:20:52 »

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 Smiley

Offline buddyBro
« Reply #17 - Posted 2017-12-18 16:19:44 »

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 Smiley

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

Click to Play
Offline VaTTeRGeR
« Reply #18 - Posted 2017-12-18 17:12:21 »

Quote
java web start

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

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 Cheesy

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.
Offline buddyBro
« Reply #19 - Posted 2017-12-18 17:44:43 »

@VaTTeRGeR Thank you so much, that was a very helpful Smiley. 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 Smiley, 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 Smiley).

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

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"
Offline buddyBro
« Reply #20 - Posted 2017-12-19 16:22:36 »

So i've updated the project to address some of the simpler / easier-to-fix concerns brought up. (http://www.java-gaming.org/user-generated-content/members/244457/monster-12-19-17.jar - see top post for updated jar)
specifically,
1) distance required between monster / exit and human to trigger game over has been decreased (from 2 to .5 units);
2) Pressing "enter" key restarts the game. At game over, text is displayed to remind the player they can press Enter.
3) Map generation can no longer generate isolated room-groups. Only group of connected rooms will be kept. This should fix unreachable exits / monsters.

The fix for slower speed when "sliding" on a wall, isn't as straightforward as I thought it would be, since the intersection finding logic solves for x movement, then y movement separately. It has no way to come back to the x-logic after it realized it's sliding on a wall in the y-direction in order to increase the x-movement. So the solution would require rewriting the movement intersection logic, which I will do, but just not in this update.

Next i will address the bigger game-design concerns, e.g., fix "repetitive & mindless wandering and hope u encounter exit before u encounter monster and feel like you're helpless in determining whether u win or lose." I've got some ideas on how i'll try to improve this, but before i'll list them below to get some opinions:

Encountering the monster shouldn't be a rare occurrence that ends in losing; it should be a probable, experience that repeatedly breaks up the monotone of searching for the room, and must therefore also be "resolvable" without defeat. First, to make it more likely to happen, the monster will not wander aimlessly when it is far from the human, but instead "sniff" the general direction of the human and move towards the general vicinity. Second, to make the encounter resolvable/conquerable, the monster will be only slightly faster than the human. In addition, the monster will not be able to chase the human's exact location even without line of sight. Instead, the monster takes "sniffs" on a ~5 or ~10 second cool-down, which provide it with the approximate location of the human (more accurate with smaller distances), and follows the last sniff location. Only when the monster has line of sight of the human (or his light), will the monster chase the exact location of the human. This gives control to the human on escaping the encounter by juking and such. In addition, the human's light can be toggled off, making it harder to navigate, but also less likely for the monster to gain line of sight of the human's light. Lastly, the monster leaves a fading "footprint" trail, to allow the human to have control on avoiding encounters.

These are just initial thoughts. In essence, I'm just trying to avoid the "inevitably" of defeat following the monster/human encounter, as well as make escaping and avoiding an active task rather than luck-based.
Offline buddyBro
« Reply #21 - Posted 2017-12-20 21:43:01 »

Updated, http://www.java-gaming.org/user-generated-content/members/244457/monster-12-20-17.jar (see top post for most updated jar).

In this update,
I've changed monster behavior. It no longer can determine the human's exact location when nearby unless it has line of sight. 1) if it has line of sight of the human, it directly chases the human. 2) else, if it's "sniff" cooldown is ready, it sniffs which gives it an approximate location of the human (accuracy vary's depending on distance) and updates it's movement to go to that approximate location
And the human now get's a blinking direction indicator when the monster is nearby. Blink frequency is relative to distance, and direction points towards monster. Lastly, human detection distance has been increased.

Hopefully these set of changes help address the almost-guaranteed "game over" on encountering the monster, as well as make encounters with the monster more frequent.

All feedback greatly appreciated Smiley
Offline buddyBro
« Reply #22 - Posted 2017-12-22 17:18:53 »

Another update Smiley

http://www.java-gaming.org/user-generated-content/members/244457/monster-12-22-17-2.jar (most up to date jar in top post)

1. Added hints; these are purple floor tiles that protrude from the exit horizontally, vertically, and diagonally every 3 tiles. They help the human find the exit more deterministically.
2. added particle system and monster "footprint" trail indicating where the monster has been recently.
3. monster speed decreased from 50% to 20% faster than human
4. camera is more zoomed out by default (z increased from 20 to 25), allowing you to see more of the map. Feel free to try adjusting this ("-" and "=" zoom out and in) and let me know what feels optimal
5. fixed bug where corridors with dead ends were being generated
6. Adjusted monster sniff error. Monster is less inaccurate at determining human's location at farther distances. It's a linear scale, with a minimum error of 5 units that increases at about .3 units of error per 1 unit of distance.
7. Stamina and Running. Stuck in a hallway with the monster right behind you? Have no fear, just press "." for a short burst of movement speed (100% increased movement speed) to get away!

Click to Play
Offline buddyBro
« Reply #23 - Posted 2017-12-23 19:53:30 »

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

I've redone the movement collision algorithm. It no longer makes you slow down if you're sliding against a wall. Turning tight corners while being chased by the monster will be a little bit less scary.
Plus improved the house generator to require a minimum number of connected rooms (set to 70). We should no longer experience the bug with just 1 or a small number of rooms being generated, and the monster, human, and exit are spawned very close by. So if anyone still experiences this bug, let me know.

All feedback greatly appreciated. Smiley
That being said, I feel like this project is coming to an end soonish; as other than making it prettier (I'm not much of an artist), and doing small fixes & improvements I don't really know where to take it. Thank you all for your feedback and helpful comments, I had fun building the project, if there are any features or ideas you would like to see before I move to my next project, let me know Smiley.
Pages: [1]
  ignore  |  Print  
 
 

 
xxMrPHDxx (306 views)
2017-12-31 17:17:51

xxMrPHDxx (94 views)
2017-12-31 17:15:51

xxMrPHDxx (146 views)
2017-12-28 18:11:33

Ecumene (310 views)
2017-09-30 02:57:34

theagentd (492 views)
2017-09-26 18:23:31

cybrmynd (528 views)
2017-08-02 12:28:51

cybrmynd (463 views)
2017-08-02 12:19:43

cybrmynd (446 views)
2017-08-02 12:18:09

Sralse (405 views)
2017-07-25 17:13:48

Archive (1312 views)
2017-04-27 17:45:51
Java Gaming Resources
by philfrei
2017-12-05 19:38:37

Java Gaming Resources
by philfrei
2017-12-05 19:37:39

Java Gaming Resources
by philfrei
2017-12-05 19:36:10

Java Gaming Resources
by philfrei
2017-12-05 19:33:10

List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!