Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411283 Posts in 69325 Topics- by 58380 Members - Latest Member: bob1029

March 28, 2024, 11:40:42 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityDevLogsProject Rain World
Pages: 1 ... 100 101 [102] 103 104 ... 367
Print
Author Topic: Project Rain World  (Read 1421813 times)
JLJac
Level 10
*****



View Profile
« Reply #2020 on: September 16, 2014, 10:39:44 PM »

*phew* Who, Me?

Update 309
Finally I think that everything having to do with AI data being saved to level files is DONE! For each creature (or rather for each "pathing template", some creatures share the same pathing data as their movement is similar) there are now several AI heatmaps that can easily be accessed. One of those is the dead end map, and then there is a dijkstra map for each room exit.



Here's a visualization where I can look at the different AI maps for all the different creatures by moving the mouse around. The ones with little blinking dots are the dead end maps, and the blinking dots are the hub spots or fleeing targets. Saving those to the file was kind of a hassle as well, until I figured out I could just shift the float upwards with 2. (Shifting it with 1 would be risky as the range is 0..1 and then it wouldn't know the difference between an actual 1 and a 0 that had been shifted.)

This means that theoretically creatures could move around between exits with no path finding at all, just by following the dijsktra maps. In practice there are other things playing a role as well, such as the Obstacle Tracker, so most of the more intelligent creatures will still need to do actual path finding. For small, stupid, swarming creatures it could definitely be used though, enabling what looks like intelligent behavior with pretty much 0 strain on the processor.

What most creatures will be able to use the maps for, however, is having a better general understanding about where they (and stuff they interact with) are in space. Which exit am I closest to? Which exit am I closer to than any other creature? Considering a group of creatures, towards which exit do they gravitate?

I have this one idea though, let me share it with you and tell me what you think. The idea is that the dijkstra maps could be used as beacons for triangulation of distances between arbitrary points on the level. What I'm talking about here is not distance as in straight distance, which is easy, but actual pathing distance with the terrain counted in. If you are close to another place in coordinates but it takes a huge detour to get there, that detour distance is pretty much the only thing that's relevant, right? I'm thinking about this especially in terms of being afraid of other creatures, when fleeing it is very relevant information how close the threat actually is in terms of time to get to you, rather than mathematical shortest distance.

I think the triangulation technique could create pretty decent estimations for these non-direct distances. To get the exact distance you'd need pathing, but this technique is probably at least 10 000 times quicker in most cases, and will hopefully produce acceptable results.

Ok, so take a look at this. Here's a dijkstra map for each exit, and I'm trying to triangulate the distance between A and B. The data I have access to is the distance between those points and each exit.



So what I'd do here is basically imagine each map as a dimension. For the first dimension, then, A is at 25 and B is at 12. That makes our delta in that dimension 13.

ABS(25 - 12) = 13
ABS(18 - 60) = 42
ABS(40 - 6) = 34

(No I didn't count tiles, the numbers are just invented)

These distances in "triangulation space" can tell us some stuff. If we only have one dimension, we can't know very much, because there are many tiles on the map that are exactly 12 tiles away from a specific exit, and they are not necessarily close to each other. E.g 12 tiles to the left of the exit and 12 tiles to the right of the exit. If we have more dimensions to play with though, I think the triangulation would quickly become more reliable. At three dijkstra maps my estimation is that it would be extremely uncommon for two tiles to have the same combination of distances to all exits, making the coordinates in "triangulation space" pretty reliable in their relationships to other coordinates. Correct me if I'm wrong here!

The system could potentially give a "false close", but never a "false far". An example of a "false close" would be if you have a room with an obstacle in the middle and an exit at the north and the south of the obstacle. A point to the west of the obstacle could have the same distance to both exits as a point to the east of the obstacle, making them appear identical or close in "triangulation space". An asymmetric placement of the exits, or a third exit, would help with that though.

A "false far" can never happen, because if the points are separated in any of the "triangulation space" dimensions, they are at least as separated in actual travel tiles as well. Look at A and B in the third picture above - the absolutely closest they could be while having the distances 40 and 6 would be if B was 6 tiles up on the same path as A, and then they'd still be 34 tiles separated.

Another way to say this is that if the deltas in all "triangulation dimensions" is 0, A and B might or might not be on the same tile, but if any dimension has a delta larger than zero, A and B are sure to not be on the same tile.

The fact that the system might give a "false close" but never a "false far" probably means that of the three deltas calculated in the example above, you should pick the biggest one, and conclude that the actual distance can be no larger than that.

I think this makes it fitting for fleeing behavior. These distances could be used to evaluate how nervous a creature should be about another creature, and whether it's time to calm down and stop the fleeing behavior. "False close" isn't too bad in this scenario, because better safe than sorry, right?

Also it will be cool to check out how this can be used in swarming behaviors. Maybe you could even create some strange kind of dynamic path finding using it, if you move towards whichever neighboring tile is the closest to your goal in triangulation space rather than in actual space.

Oh, when I read through my post before hitting the button I had a small epiphany! One way to further eliminate "false close" could be to add the mathematical straight distance between A and B and treat it exactly like one of the triangulation dimensions! It has the exact same properties - ie that A and B can't be closer than that, so it would work really well as a last reality check, eliminating for example the "obstacle in the middle and symmetrical exits on each side" problem. Shortcuts messes this up a little bit as they make it possible for tiles to be "closer than they actually are", so maybe it shouldn't be relied upon too much. But shortcut travel still takes some time, so it could be counted in to some degree...
Logged
JLJac
Level 10
*****



View Profile
« Reply #2021 on: September 16, 2014, 11:33:40 PM »

Dijkstra map triangulation looking pretty good!



The color of each tile is how far that tile is estimated to be from the mouse pointer. It uses the largest distance it can find.

I have a bit of a heuristic approach here, where the it counts 1/3 of the straight line distance as one of the dimensions, meaning that straight line distance is accounted for, but not taken quite as seriously as the triangulation dimensions. This looks like a good balance to me, as if I didn't account for straight line distance at all it would display some pretty obvious weird artifacts and errors, but if I counted it in fully it would not leak through shortcuts at all.

Contrary to what I expected the algorithm does give some "false far" outcomes, in cases when all the exits are close to each other. This can be helped by giving the straight line distance more weight. I'm thinking though, maybe I shouldn't actually just pick the largest value - instead I could try to calculate the multidimensional diagonal in triangulation space?  Evil

It is pretty cool though! It gives an estimation of a dijkstra map between any two points that's decently accurate, and at 0 memory cost and 0 processing cost. The way to do this "properly" would be to move around a dijkstra map target every time it changes tile, do a complete flood fill, and save a huge grid of those values, just to throw it away on the next movement. Slow, weighty, and it couldn't really be done for more than a few moving entities. This system can estimate distances between all and any points on the fly! I do these calculations for every tile times every frame! With this system I could easily have 100 creatures asking for the distance to all 99 other creatures each frame, and it wouldn't even be a problem.

Gonna try my hands at those multi-dimensional diagonals now ...
Logged
Belimoth
Level 10
*****


high-heeled cyberbully


View Profile
« Reply #2022 on: September 16, 2014, 11:36:59 PM »

Nice. You should do a visualization of the difference between estimated and actual dijkstra maps because that would be cool.
Logged

JLJac
Level 10
*****



View Profile
« Reply #2023 on: September 16, 2014, 11:59:58 PM »

Yeah! These are actually far from perfect - if you look at the gif you might notice that there's some snapping going on at places. That's where one of the dijkstra maps approach the area from two different directions. Those tiles are considered far apart despite actually being close. The less dijkstra maps it has to work with and the closer they are the more stuff like that. But given the extreme benefits in speed and memory I think that's worth it by far. For AI's that are supposed to be a bit smarter you could maybe have a real dijkstra map being updated close to themselves or the threat they're avoiding, and then resort to the triangulation for the rest of the level.

Multidimensional diagonals worked out fine, the estimation looks a bit smoother. They're probably a bit slower as they have some exponents and a square root (it's actually just Pythagoras's theorem in n dimension) but that's still so vastly faster than creating actual dijkstra maps that it's not really anything to think about.

It will be interesting to see how the AI will be able to use this!
Logged
gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #2024 on: September 17, 2014, 06:02:45 AM »

Wait the triangulation is that:
- for each tile
- store a djikstra distance to all exit?
While creature evaluate pathing
- check the djikstra distance of neighbor tile to the desired exit
- follow the lowest number

Is that right?
Logged

JLJac
Level 10
*****



View Profile
« Reply #2025 on: September 17, 2014, 03:14:47 PM »

That would be generating and following a dijkstra map - every tile knows its distance to a fixed origin point. The triangulation is about comparing multiple overlapping dijkstra maps to estimate the distance between any two arbitrary coordinates. This means that I can get an approximation of a dijkstra map for any point with just a few lines of code executed and no memory usage, contrary to executing the tens of thousands of lines of code necessary to generate an actual dijkstra map and save it to memory.
Logged
gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #2026 on: September 17, 2014, 03:26:39 PM »

What's the origin of all the baked djikstra maps? Exit?
Logged

JLJac
Level 10
*****



View Profile
« Reply #2027 on: September 17, 2014, 03:38:08 PM »

Yep! The more baked maps, and the more apart their origins, the more accurate the triangulation becomes.

What the system doesn't account for however is one-way connections, as it's just comparing distances it doesn't know the difference between positive or negative distance, or what kind of connections the distances go through.
Logged
JLJac
Level 10
*****



View Profile
« Reply #2028 on: September 18, 2014, 01:18:26 AM »

Update 310
So I got some flight behavior up and running. The core mechanic is an engine that can identify a "threat level" for any given tile, like so:



Sorry about the coloration in these ones, it's a bit unintuitive as I didn't invert the hues. Red is less threatening, and blue is very threatening. The map is generated by a combination of straight distance and dijkstra triangulations.

The system supports many different threats which can be assigned separate severity. In this next gif there's one threat emitter assigned to the mouse pointer and another stationary - they tend to melt together if they get close.

The dead end map is consulted as well - you might notice how some tiles are always considered a bit threatening. Basically dead end tiles get a "bonus" on their threatening level.



The flight behavior consists of picking an (accessable) coordinate every frame, and comparing it to the current destination of the path finder. If the new point is less threatening than the last one, the new one is assigned. There's a 50% chance to evaluate one of the pre-baked "hub spots", otherwise it'll pick a coordinate from anywhere in the room. I'll also have it consider exits here later, making the creature able to flee from the room rather than just within it.

The path finder assigns a harsh cost to tiles that are considered threatening, meaning that the paths will take detours to avoid them. I have an exponential formula to this, making it almost impossible for it to path through a threat area.

Here's a blue lizard feeling very afraid of the mouse pointer.



The lizards are not good at crawling backwards, and avoid it for the most part, but if they have a nearby threat right in front of them they'll back up. This will activate a "panic mode", lasting a second or so, where they won't path to any specific target, but just move to whichever nearby tile is considered the least threatening.

The system is perhaps not perfect, but I think it's good enough for most purposes. The goal here isn't as much to create an actual super efficient fleeing behavior as it is to communicate that the creature is trying to escape. From a game fun perspective it is probably always more fun for a non-player entity to actually bite the grass rather than successfully getting away (Action happens! Something gets eaten! And it wasn't you!) so as long as the behavior doesn't look frustratingly stupid I'm happy with it. Now to contemplate what to do next... Flies?
Logged
jgrams
Level 3
***



View Profile
« Reply #2029 on: September 18, 2014, 04:47:10 AM »

Edit: Yay! http://dinodini.wordpress.com/2010/04/05/normalized-tunable-sigmoid-functions/
It actually really isn't a sigmoid I think, as it doesn't have e^-x, but it fulfills the same purpose.

Bah. I should pay more attention to this devlog. I just derived my own x/|x| style sigmoid curve, and that would have saved me a bunch of time. Interestingly, I took sort of the opposite approach from that article, using a parameter from 0 (straight lerp) to 1 (step function), giving y = x / (1 + k*abs(x) - k) and using its inverse for "negative easing". HTML5/Canvas demo...

I am loving all these maps. I've just spent way too much time staring at them.
Logged
gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #2030 on: September 18, 2014, 11:46:53 AM »

Haha that lizard really look panicked with all these hesitation!
Logged

Reilly
Level 2
**


14/f/tx


View Profile WWW
« Reply #2031 on: September 18, 2014, 12:52:33 PM »

Haha, the panicked drops really sell it.

Poor guy.
Logged

ofx360
Level 0
**


View Profile
« Reply #2032 on: September 18, 2014, 04:32:06 PM »

I actually feel bad for the little guy, so it seems like you have a success on your hands
Logged
JLJac
Level 10
*****



View Profile
« Reply #2033 on: September 19, 2014, 12:11:51 AM »

Haha yeah - I think it'll be pretty cool when you've been antagonized by those guys for a while to suddenly see them flee from either yourself when you've managed to hurt a few of them with a spear, or some larger creature hunting them.

Update 311
Spent the day cleaning up the fleeing behavior - I had stupidly been using just 2D coordinates throughout the entire system, making it unable to differentiate between rooms and making creatures potentially confused by threats in other rooms. Now it's using world coordinates, that have the room index specified.

Now the threat tracker can create a link to the creature tracker as well, which I didn't really have a framework for yesterday. This means that a creature can avoid another creature using its tracking data, and I can easily set up links like that when the AI is alerted that a new creature has been spotted. As the time since the threatening creature was seen increases, the threat will decrease accordingly, until it's forgotten altogether.

Also enabled fleeing between rooms. If a fleeing creature realizes that there's an exit with no threats blocking it, it might just leave.

Have a nice weekend! Here's a gif of Reverse Rain World!

Logged
Franklin's Ghost
Level 10
*****



View Profile WWW
« Reply #2034 on: September 19, 2014, 08:40:58 AM »

That Reverse Rain World is great, should be a little mode you can unlock in the game. Have to hunt down as many lizards as you can with your little buddies and one who catches most wins.
Logged

Thomas Finch
Level 8
***


@slowcircuit


View Profile WWW
« Reply #2035 on: September 19, 2014, 05:57:24 PM »

There could be a pac-man reference hidden in the game. You can find a big floating white ball and when you eat it, all the lizards start blinking faster and running away from you for a minute.
Logged

JLJac
Level 10
*****



View Profile
« Reply #2036 on: September 22, 2014, 03:34:11 AM »

Update 312
Some pretty interesting parts have started moving into place today. First and foremost, a framework for relationships between species. A relationship is a one-way link between one Creature Template and another, consisting of a type enumerator and a float signifying intensity. Currently I have Ignore, Eat, Afraid as possible relationship types, but there are endless possibilities such as AggressiveRivalry, Annoyed, Symbiotic, KillForFun, Cautious, Territorial, and so on. These are the threads that will hold this food web together.

As you might remember the Creature Templates have some inheritance between them - for example there exists a Lizard template that's never incarnated on a level, but which is an ancestor of all the lizard breeds. I've set the relationship system up to flow down through the inheritance tree, and overlap empty ("Ignore") relationships but never specifically declared relationships. I'll have you know that I did this with a recursive method! (On declaring a relationship, check all children if they have any relationship to the relationshipee, if not, call the method again but on the child! I only got stack overflow exceptions 5 times setting it up!)

This means that I can first declare that all lizards should eat slugcats and ignore each other, by addressing the ancestor Lizard object. Then I can create exceptions, like making Green lizards hunt Blue lizards, making Pinks aggressive towards each other, or deciding that Greens should actually run away from slugcats rather than hunt them.

The really cool part about today though is that I've been able to start hooking the AI components to some behavior. Everything was pretty much in place already, so it was very easy to make the lizards actually react to other creatures. As I had planned, it seems like I can create lizard behavior with very little code in the actual lizard AI, as almost everything is outsourced to the different modules.

So for example there is a Threat Tracker, right? And from today a Prey Tracker as well. The general AI already has a method that is "a creature has been spotted". So what the lizard AI does is that each time it gets notified about a new creature it checks with the Creature Template Relationships: if the alien creature is prey, it notifies the Prey Tracker - if it's a threat, the Threat Tracker is notified.

These modules are then pretty much autonomous, they run their own behaviors alongside the main AI, keeping track of threats and potential prey respectively. Every frame the main AI can ask them, however, for a status report. The Threat Tracker can be asked for a threat level 0-1, and the Prey Tracker can similarly be asked how it estimates the chances of catching its most attractive prey within the next few frames.

Using these values, the main AI can do a utility based decision - what's more urgent? If the threat tracker tells me that I'm actually in danger here, perhaps I should activate the Fleeing behavior? The idea here is that these values should be weighted when compared, for example a threat level of 0.3 might be more important than an estimation from the Prey Tracker at 0.7, as self-preservation should be prioritized. Later when more elements are in, the threat of rain could perhaps overshadow the threat of another creature, etc.

So say that the utility check decides that the current threat level is the most urgent issue - in that case the fleeing behavior is activated. When the fleeing behavior runs, the main AI once again turns to the Threat Tracker, this time asking for specific details on where to run. The Threat Tracker then does its calculations and returns a flight path, while the Prey Tracker can be more passive this particular frame.

Then there's of course talk between the modules, all of which is moderated by the main AI. For example the Path Finder will ask the main AI about each tile it handles, whether or not the main AI wants to add some path finding cost to that particular tile. The main AI will then ask other modules, such as the Obstacle Tracker or Threat Tracker, and for example return higher costs to tiles that are perceived as more threatening.

It all seems to work! A hunter/prey relationship between Green and Blue lizards makes one pursue the other, but both still hunt the player on opportunity, for example. It's a lot of fun to be able to switch these relationships on an off at a whim. Right now there's no real interactions in yet, so they can't bite each other or the like, but it's still fun to watch them react to each other.

What's fun about the AI system is that it seems I have somewhat been able to separate the more technical stuff from the design stuff - out in the modules calculations are done, while in the main AI there are only a few lines of code, but those lines are creative content rather than technical solutions. Using the modules I can quickly and cleanly create behavior that conveys personality, such as cowardice or brute force, rather than solving a lot of technical problems. I'm much looking forward to creating more creatures within this framework!

All of this is very hardcoded and crude as is, but I soon hope to be able to show you some more sophisticated stuff.
Logged
Vadinci
Level 0
**



View Profile
« Reply #2037 on: September 22, 2014, 04:06:12 AM »

A quick question that popped up: How do the blue lizards react to the green ones? Did you make them afraid of green ones by default, or do they realise that they are being hunted and then register the hunter as a threat? Or maybe they are just completely oblivious to the fact that they are about to be eaten?  Shrug

I also loved the lizard backing up when he suddenly sees the slugcat below him in the reverse rain world gif! The way you handle the AI makes the creatures feel truly alive!
Logged
Zorg
Level 9
****



View Profile
« Reply #2038 on: September 22, 2014, 04:15:16 AM »

Sounds really cool.

Are multiple lizards of the same color able to hunt cooperatively? For example not choosing the same path and/or keeping a constant distance to each other?
Logged
Adam_
Level 1
*



View Profile WWW
« Reply #2039 on: September 22, 2014, 01:39:51 PM »

I must admit that I haven't read all of the 102 pages, but just wanted to say that I really like the style of this project. It looks awesome and, judging from the gifs you're posting, has a great feel to it. Any chance to get an ETA on when this game will be released? Smiley
Logged

Pages: 1 ... 100 101 [102] 103 104 ... 367
Print
Jump to:  

Theme orange-lt created by panic