What's everyone working on? (tigsource inspired)

[Germanunkol]

Working on a business management game, will probably be a mall management in the style of rollercoaster tycoon / transport tycoon

Looks great! Already reminds me of those games...

[Rukiri]

Working on a business management game, will probably be a mall management in the style of rollercoaster tycoon / transport tycoon

Make this happen! Loved those type of games!!

[Jasoco]

Working on a business management game, will probably be a mall management in the style of rollercoaster tycoon / transport tycoon

I was planning on making a Mall Simulator of my own one day. I've started a few prototypes but never could get myself to finish or continue.

One day.

Maybe.

[sashwoopwoop]

Thanks guys I'm currently struggling with the path finding and visitor movement. But it's slowly getting there. I want it to be a 6 month project, let's see how far I can get

[Jasoco]

Thanks guys I'm currently struggling with the path finding and visitor movement. But it's slowly getting there. I want it to be a 6 month project, let's see how far I can get

There's an A*Star for Lua out there. But the problem I encountered myself at the time was that it uses a lot of processing cycles for each instance so having a lot of moving pathfinding entities kept pausing the code. So I had to modify it to use coroutines, which allowed the pathfinding code to run parallel to the game and the entity wouldn't start moving until its path was calculated, but the game also wouldn't pause either.

Here's that project I created a while ago. (Apparently around the time the first Hunger Games movie was coming out from the looks of one of the character names in the code) I had to modify it to work outright in 0.9.1 because it's outdated. It has a lot of crappy code in there you won't need. Just try and look at the pathfinding and behavior files. I dunno. Maybe it'll be of some use to you. It even had a level editor that no longer works and a menu system you won't even see anymore because I had to edit the code to skip right to the game itself after modifying a few lines for 0.9.x.

Coroutine Pathfinding.love

(205.32 KiB) Downloaded 152 times

I haven't tested it with a super huge amount of entities though. A mall simulator would need a lot of moving entities, i.e. customers, and I haven't gone that far as to have that many. Your version would be different though as you wouldn't want to have each entity check for collisions with each other. Whereas my project above did.

I did just test it out with 50 entities (+ 2 or 3 NPCs) all finding paths of their own and yes, while they will stand in one place for a while they find a path, it's probably because my code just tries to find a proper empty square first before calculating the path so it might just be hitting solid blocks a lot. Your code would probably already know where the ending points should be and won't do this. Either way, it handled 50 entities fine. (Changing it to 100 worked well too. But at 500 the screen was filled with enemies so I couldn't test it. But it still seemed responsive.)

Notes:
At some point I broke the ability to move down a screen. But you can move to the next screen to the right. Not that it matters for this code.
Also, I haven't tested this with anything larger than the small grid you see here. The pathfinder might take a much longer time with large grids.
This is a few years old. I don't know if newer better pathfinding algorithms for Lua have come out since. But if they have Coroutines then they'd be awesome.
Good luck.

[sashwoopwoop]

There's an A*Star for Lua out there. But the problem I encountered myself at the time was that it uses a lot of processing cycles for each instance so having a lot of moving pathfinding entities kept pausing the code. So I had to modify it to use coroutines, which allowed the pathfinding code to run parallel to the game and the entity wouldn't start moving until its path was calculated, but the game also wouldn't pause either.

Cool, thanks! I'll definitely use the subroutine part. I'm using Jumper (https://github.com/Yonaba/Jumper) and I'm surprised by the performance. I played around with it and with 2000 entities I did not get fps drops (even though I did all the pathfinding stuff in the main thread). We'll see how it works with more complicated maps

[Roland_Yonaba]

@Jasoco: Hats off, that is a very clean example. It is simple, yet deadly efficient. Actually, it is an implementation of time-sliced pathfinding. I am now really sure on how this would scale, though. I do not worry about the technique, but mostly about the actual implementation. It might get slower and slower with increasing number of entities (IMHO, I didn't make any test). In that case, you can gain noticeable speed using a more appropriate data structure for your openlist, such as a binary heap.

Can you please, by the way, give me a bit more explanations on the heuristic you are using ?

Code: Select all

local function dist( startx, starty, currx, curry, targx, targy )
    local dx1, dy1 = currx - targx, curry - targy
    local dx2, dy2 = startx - targx, starty - targy
    local cross = abs(dx1*dy2 - dx2*dy1)
    return (abs(targx-currx) + abs(targy-curry)) * (1+(cross*0.001))
end

It looks like manhattan, plus a little tie-breaker, too me.
And also, the meaning of cap variable ? It looks like the distance of the segment start->current->goal multiplied by ... 5 ?

Cool, thanks! I'll definitely use the subroutine part. I'm using Jumper (https://github.com/Yonaba/Jumper) and I'm surprised by the performance. I played around with it and with 2000 entities I did not get fps drops (even though I did all the pathfinding stuff in the main thread).

Wow. I am pretty much surprised with these results ... Maybe you are pathing on very small maps ?

[Plu]

Considering it's Jumper, probably a mostly empty map. The image he posted is basically just 2 rectangles; Jumper will be incredibly efficient there. It'll start dropping in performance when you add rooms, though.

What kind of test case did you have sashwoopwoop?

[chezrom]

@Roland

In fact the distance formula is the manhatan distance between the current and target point, multiplied by a factor that favored the fact that the current point is aligned with the start and target point.

"cross" is in fact the cross product or determinant of two vectors : current to target, and start to target. This is zero when the two vectors are colinear and maximum when the vectors are perpendicular.

[sashwoopwoop]

What kind of test case did you have sashwoopwoop?

Very simple test case indeed. only like 10 out of 256 tiles were walkeable. But it won't get very complicated, so I guess / hope I won't run into performance issues there.

I'm pretty impressed by this guy's "Trace" algorithm: