IRC logs for #openttd on OFTC at 2018-05-18
⏴ go to previous day
00:19:10 *** rocky1138 has joined #openttd
00:54:27 *** ZeNinja864 has joined #openttd
00:57:52 *** Thedarkb-X40 has joined #openttd
01:21:57 *** gnemonix has joined #openttd
01:34:11 *** snail_UES_ has joined #openttd
02:39:49 *** ToBeFree has joined #openttd
03:06:54 *** snail_UES_ has joined #openttd
03:07:51 *** snail_UES_ is now known as Guest2977
03:07:51 *** snail_UES_ has joined #openttd
04:00:31 *** ToBeFree has joined #openttd
04:28:45 *** muffindrake1 has joined #openttd
04:41:09 *** Smedles has joined #openttd
05:06:10 *** Supercheese has joined #openttd
05:56:15 *** sla_ro|master has joined #openttd
07:00:00 *** Supercheese has joined #openttd
07:09:35 *** dustinm` has joined #openttd
07:56:36 *** andythenorth has joined #openttd
08:07:45 *** Wacko1976 has joined #openttd
08:53:57 *** andythenorth has joined #openttd
08:56:31 * andythenorth needs to learn to type, quite badly
09:36:41 *** andythenorth has joined #openttd
10:10:49 *** TheMask96 has joined #openttd
10:21:51 <andythenorth> how do you apply a gist anyway/
10:22:18 <andythenorth> damn keyboard now working, there's a class action suit against fruit company now
11:39:09 *** muffindrake has joined #openttd
11:41:51 *** andythenorth has joined #openttd
12:14:29 <peter1138> Has anyone ever got anywhere with clustering for pathfinding for ships?
12:25:26 *** WWacko1976-work has joined #openttd
12:25:45 <Eddi|zuHause> i think there were one or two patches, ages ago
12:33:15 <andythenorth> there's a ship separation path
12:33:21 <andythenorth> tries to keep them on separate tiles or something
12:50:07 <Eddi|zuHause> that's something completely different
12:53:04 <andythenorth> does peter mean caching paths?
12:53:12 <andythenorth> for performance?
12:53:23 <andythenorth> I though he had a patch for that :P
12:53:43 <Xaroth> Wait, he doesn't have a patch for that?
12:53:53 <Eddi|zuHause> "clustering" means "treat large bodies of water as one block"
12:55:05 <Eddi|zuHause> large bodies of water have the problem that there are lots of paths through them which have equivalent lengths, making pathfinding very inefficient
12:55:22 <Eddi|zuHause> if you can reliably identify these blocks
12:55:35 <Eddi|zuHause> then you can reduce the complexity/search space of the pathfinder
12:56:21 <andythenorth> how is a block bounded?
12:56:37 <andythenorth> it's arbitrary how any connected body of water is sliced into blocks
12:56:43 <andythenorth> unless a heuristic is proposed :P
12:57:00 <andythenorth> human brain would want to reduce it to things that look like seas or lakes
12:57:09 <andythenorth> but the maths might not work that way
12:57:31 <peter1138> Yeah, that's why I'm asking :-)
12:57:32 <Eddi|zuHause> i would imagine making rectangles
12:57:32 * andythenorth wonders if there's a vector space for it
12:57:40 <peter1138> It's start with 16x16 chunks or something like that.
12:57:54 <Eddi|zuHause> smallest rectangle is one tile
12:57:57 <peter1138> But yeah, it doesn't exactly fit.
12:58:03 <peter1138> I have a patch to cache paths.
12:58:04 <Eddi|zuHause> and then you merge adjacent rectangles
12:58:09 <Eddi|zuHause> until you have nothing left to merge
12:58:15 <andythenorth> for every tile, there are vectors to every other tile
12:58:20 <andythenorth> some vectors will cluster
12:58:24 <peter1138> It actually works really well, until the landscape gets change.
12:58:37 <andythenorth> vectors are probably computationally intense, and demanding on RAM
12:58:50 <andythenorth> we made a vector space for YouTube videos once :P
12:58:58 <peter1138> Save/load would be an issue of course.
12:59:43 <peter1138> I can solve some pathfinding cpu consumption issues simply by limiting the code to not bother pathfinding if the distance is greater than the existing max-order distance.
12:59:58 <peter1138> (That check is only there when adding orders, not when pathfinding.)
13:00:30 * andythenorth has randomly stupid ideas
13:01:02 <peter1138> This leaves one (afaik) remaining issue: trying to pathfind to an unreachable destination which is within that limit is still very expensive.
13:01:23 <andythenorth> but we could also just make the game build navigation points (lighthouses) on a grid, and everybody has to route ships 'via flinborough lighthouse' or whatever
13:01:32 <andythenorth> replacing silly buoys
13:01:56 <andythenorth> divide the map into sectors somehow, of fixed size
13:02:40 * andythenorth back to GDPR fun
13:03:16 <Eddi|zuHause> there was a patch once that placed random buoys on the map and divided the water into regions that way
13:03:31 <peter1138> fixed-size sectors break when you have areas within a sector that are separate don't reach.
13:03:42 <Eddi|zuHause> so pathfinding across multiple regions would just go between buoys
13:04:00 <peter1138> Eddi|zuHause, interesting.
13:04:21 <andythenorth> having to place buoys is really annoying for some reason
13:04:29 <andythenorth> it's very hard to predict which routes will need them
13:04:32 <peter1138> But you have to know which automatic buoys are reachable, I suppose.
13:04:44 <peter1138> But that can be a much smaller search area.
13:05:13 *** snail_UES_ has joined #openttd
13:05:39 <peter1138> There's the "flood fill regions to determine reachability" but that requires additional storage and needs to be updates when the map is changed.
13:06:15 <peter1138> And that only 'solves' the unreachable case, not 'difficult' paths.
13:07:01 <peter1138> Region index, heh. There we go.
13:07:42 <peter1138> That could be exceeded, I guess.
13:09:52 <Eddi|zuHause> well, you could just cut out the smallest regions, and fall back to tile mode
13:24:55 <Eddi|zuHause> another attempt to cut down on ship pathfinding cost is to reduce the number of pathfinder calls by storing the found path (kinda like reservations), instead of rerunning the pathfinder on every tile
13:25:38 <Eddi|zuHause> on a first approximation, store in each ship "go in a straight line for X tiles"
13:26:15 <Eddi|zuHause> all tiles inbetween would skip the pathfinder call, and just choose the continuing trackbit
13:26:43 <peter1138> Yes, that works, I have a patch for it :p
13:27:07 <peter1138> Just has issues when landscape is changed currently.
13:27:15 <peter1138> And of course not multiplayer safe.
13:27:33 <peter1138> (I couldn't easily figure out how to save a std::stack :-))
13:29:07 <Eddi|zuHause> well, doesn't need a stack if you just store the first leg of the path
13:31:40 <peter1138> Also doesn't work for my current worst-case of unreachable destination.
13:32:02 <peter1138> Well, the pathfinder works on trackbits, not directions, so you basically need to store each tile as a step.
13:32:18 <andythenorth> anyone want an SRE job? o_O
13:32:29 * andythenorth is taking long shots :P
13:34:05 <Eddi|zuHause> peter1138: well, a "direction" is either a sequence of the same straight trackbit, or an alternating sequence of diagonal tackbits
13:36:30 <Eddi|zuHause> it should also be easy to adjust pathfinder penalties to try to minimize turns
13:38:28 <peter1138> Also wondering about making ships take turn pathfinding.
13:38:41 <peter1138> Cos setting 100 ships off at once causes mayhem.
13:39:06 <Eddi|zuHause> one-ship-per-tile would solve that?
13:39:16 <Eddi|zuHause> or, per trackbit
13:39:25 <peter1138> With a massive drawback.
13:40:16 <Eddi|zuHause> it would suffice to impose that limit on leaving a dock
13:45:27 <andythenorth> forcing a delay on ships leaving dock/depot might be really interesting
13:45:41 <andythenorth> just enough to fix some ship problems without nerfing them totally
13:46:04 *** andythenorth is now known as Eddi|zuHause2
13:46:11 *** Eddi|zuHause2 is now known as andythenorth
13:46:43 <Eddi|zuHause> i would never say that
13:47:08 <Eddi|zuHause> *cough*state machines*cough*
13:47:41 <Eddi|zuHause> but that also has nothing to do with the topic discussed here
13:57:26 <andythenorth> each tile is a state machine :P
13:57:36 <andythenorth> how about 'seas' that are state machines :P
14:00:01 <andythenorth> why can't Google find an image of the hexagonal columns that naturally form in boiling oil?
14:03:15 *** synchris has joined #openttd
14:16:02 *** sim-al2 has joined #openttd
14:16:10 *** chomwitt has joined #openttd
14:27:39 <andythenorth> peter1138: is that a koan of some kind?
15:09:13 <Eddi|zuHause> peter1138: pathfinding through statemachines will be another crazy nightmare :p
16:00:00 *** Alberth has joined #openttd
16:00:00 *** ChanServ sets mode: +o Alberth
16:13:58 * peter1138 grumbles at irc channels switching to gitter. Pain in the arse :(
16:15:34 <LANJesus> does gitter have an IRC gateway?
16:16:43 <peter1138> Seems they do but you need to login and shit :S
16:19:49 <peter1138> I'll give it a go, thanks for pointing it out :p
16:25:35 <Eddi|zuHause> what's a gitter?
16:29:58 <LANJesus> well yeah, i'd expect some kind of authentication for gitter
16:30:07 <LANJesus> they better support sasl ; )
16:46:42 <peter1138> No need, SSL is better.
16:51:35 <LANJesus> i use CertFP/SASL when possible. no password needed
16:52:06 <LANJesus> authentication based on my SSL fingerprint
17:01:26 *** Thedarkb-X40 has joined #openttd
17:07:35 *** argoneus has joined #openttd
17:08:13 <FLHerne> peter1138: I did wonder at one point why virtually all ship paths can't be cached
17:09:12 <FLHerne> Unlike the other ground vehicles, they don't collide or anything, so the best path between two tiles will never change unless someone landscapes the map
17:10:51 <FLHerne> And the actual number of docks/buoys/water-industries served is relatively low, so it would be perfectly feasible to simply cache the complete path for every pair
17:10:53 <Alberth> or until you implement ship collision avoiding like hackalittlebit did
17:11:25 <Xaroth> Ship collision would be neat
17:11:26 <FLHerne> (on first use, so you only store the pairs that are actually used, obv)
17:12:00 <Alberth> the killer is more in lost ships, I think
17:12:18 <Alberth> which by definition is not a known path :p
17:12:29 <Alberth> and it's tried every frame
17:12:40 <peter1138> Well, every new tile.
17:13:02 <peter1138> I've "solved" the other cases, it's just the unreachable case which sucks CPU now.
17:13:45 <FLHerne> peter1138: Well, can't /that/ be cached until someone flips a water bit?
17:14:03 <FLHerne> If it was unreachable before, it'll stay unreachable until there's more water
17:14:13 <peter1138> Yeah but where do you cache it?
17:15:26 <Eddi|zuHause> you just store a body-of-water-ID in the map?
17:15:56 <peter1138> Eddi|zuHause, yeah, that link you gave earlier might be useful.
17:16:16 <Alberth> switching to JPS would remove most of the open/closed list operations
17:16:17 <FLHerne> VF_PATHFINDER_LOST is already a thing, right?
17:16:20 <peter1138> Looks like a big patch though.
17:16:42 <peter1138> FLHerne, yeah, it's not a problem for 1 ship
17:16:48 <FLHerne> So my idea is that you have a global (well,per-map...) flag for whether someone poked a water bit this frame
17:16:56 <peter1138> But when you have 200 all trying to do it...
17:16:59 <FLHerne> Oh, I see the problem
17:17:11 <FLHerne> Meh, I'll carry on explaining first :P
17:17:20 <peter1138> They'll still all do the pathfinding and cause a freeze.
17:17:34 <peter1138> Maybe we should lower the node limit :-)
17:17:52 <peter1138> It's 10000 at the moment.
17:18:24 <Eddi|zuHause> but!! 16kx16k maps with ships going one trip around the map border?
17:18:27 <FLHerne> Have the build-water and flood operations set that bit
17:18:33 <Alberth> have a max number of ships doing pathfinding each round, others are queued
17:18:39 <Eddi|zuHause> 5k ships, of course
17:18:52 <peter1138> I think the pathfinder could do with a max-distance check as well.
17:18:59 <FLHerne> Then when doing pathfinding, if (this ship is lost) and (water hasn't changed), skip
17:19:07 <FLHerne> Because it'll always fail
17:19:07 <peter1138> Alberth, yeah, I've considered that.
17:19:27 <Alberth> FLHerne: but it moved to a new tile, it may be findable now
17:19:47 <FLHerne> Alberth: Only with the distance limits, which are a stupid hack
17:20:15 <Eddi|zuHause> FLHerne: sometimes ships are lost because of dead ends/90° turns disabled/whatever that is dependent on the ship position
17:20:44 <peter1138> If you want to remove the distance limits, you need a different path finder.
17:21:16 <peter1138> Alberth, any idea how to add JPS? :)
17:21:20 <FLHerne> Eddi|zuHause: And that's bloody annoying when ships get 'lost' in canal basins and rivers for three tiles until they change direction and sort themselves out
17:21:41 <FLHerne> The PF should know about reversing
17:21:42 <andythenorth> 'just' enable 90º turns
17:21:49 <andythenorth> it's a stupid feature anyway :)
17:22:18 <Eddi|zuHause> FLHerne: imho the 90° thing is just pointless, and ships should be able to turn in-place
17:22:23 <peter1138> 90° turns should be allowed for ships.
17:22:38 <andythenorth> it's even realism :P
17:22:45 <FLHerne> The problem I saw was that ships don't pathfind every frame, so a single 'changed' flag would get missed
17:22:52 <FLHerne> There do seem to be other ones
17:23:10 <peter1138> Pathfinding every frame would make it worse
17:23:10 <Eddi|zuHause> i don't have a clue who came up with the idea that 90° turns should apply to both trains AND ships
17:23:12 <FLHerne> Eddi|zuHause: Ok, that's a better idea
17:23:18 <Alberth> peter1138: JPS assumes center of tile as position, while we use center of edge, so jps assumes 8 directions, we have 6. That's the biggest adaption to make.
17:23:29 <Alberth> otherwise, jps is quite easy
17:25:38 <Alberth> in the diagonal case, jps branches out both horizontally and vertically, while we probably would do only one direction
17:26:48 <Alberth> no idea how that article is related to artificial-intelligence :p
17:27:32 <Eddi|zuHause> pathfinding is a basic AI topic...
17:28:04 <Eddi|zuHause> AI is not just neural networks :p
17:30:48 *** Thedarkb has joined #openttd
17:31:50 *** frosch123 has joined #openttd
17:32:31 *** Wormnest has joined #openttd
17:45:39 *** TheMask96 has joined #openttd
17:55:20 <Alberth> hmm, they mangled the code layout :(
18:13:32 *** Progman has joined #openttd
18:23:14 <nielsm> okay maybe I should actually ask this... does anyone know if original TTD has any preferred timer frequencies for frame lengths or anything like that?
18:23:59 <nielsm> because in my DOS music decoding code I've just sort-of guessed that 6.5 ms gives a good approximation of the correct tempo, when I decode a "frame" of music on that interval
18:24:27 <nielsm> but there might be a more correct value hidden somewhere
18:29:37 <nielsm> hmm there is actually a magical number 148 as part of the tempo code in the music decoder, maybe that's the actual rate intended, since 148 hz = every 6.757 ms
18:31:57 <nielsm> (I don't see the "music frame rate" directly in the disassembly of the DOS music driver, since that gets called as an interrupt from the game, and the main game engine is responsible for the timing of that interrupt call)
18:46:28 <nielsm> yeah 148 hz does seem to match the tempo of the windows version midi files perfectly, based on just a listening test
18:55:44 <peter1138> Hmm, so only allowing one ship out of a depot a time helps.
18:56:41 <peter1138> Spreads out the pathfinding a bit.
18:57:05 <peter1138> With 100 ships it even still goes faster in FFWD.
18:57:41 <peter1138> Adds a bit of a bottleneck though.
19:01:44 <Alberth> they eventually do spread themselves out over the route anyway :)
19:05:08 <peter1138> Middle commit is shitty with the table in it. Couldn't see an equivalent function :p
19:08:04 <peter1138> So not quite a fix for ship pathfinding, just a series of kluges.
19:14:29 *** sla_ro|master has joined #openttd
19:15:05 <peter1138> Hmm, continue coding, or Minecraft?
19:48:47 *** andythenorth has joined #openttd
19:53:05 <peter1138> I guess he's reviewing NRT
19:53:31 <andythenorth> I think we should just commit tbh
19:53:35 <andythenorth> and sweep up the mess later
19:53:43 <peter1138> Time to prune my tree farm.
19:58:50 <Xaroth> but it used to be fun to send out 500 ships at the same time :(
20:02:43 <andythenorth> wondered when you'd mention that
20:02:58 <andythenorth> there are very high res images linked from Eurobricks
20:03:06 <andythenorth> I'm buying the forest harvester, it's really awful
20:24:32 *** gelignite has joined #openttd
20:38:57 *** ChanServ sets mode: +v tokai
21:03:42 <andythenorth> playing tanks again
21:07:57 <peter1138> Good ol' Blitzkrieg
21:18:20 <andythenorth> maybe alberth knows how ottd GUI works?
21:18:30 <andythenorth> credits say he's a GUI Wizard or something :)
21:18:52 <Alberth> I didn't write that credits :p
21:25:01 <nielsm> maybe they meant to say lizard
21:29:05 <Wolf01> <andythenorth> new valve <- I hope is easier to motorize
21:29:17 <andythenorth> looks made for it
21:29:34 <Wolf01> I don't want to put a servo for that... servos drain battery really fast
21:29:39 <andythenorth> now just need an S motor
21:30:16 <andythenorth> they made nearly everything ever wanted
21:30:21 <andythenorth> new pneumatics, all that jazz
21:31:27 <Wolf01> I still need to build the BWE :(
21:31:34 <andythenorth> only thing I lack is an S motor
21:31:38 <andythenorth> all other ideas covered
21:32:26 <Wolf01> I would like PF valves
21:33:03 <andythenorth> bit too specialised imho :)
21:33:09 <andythenorth> and probably $$$$
21:34:45 *** Progman has joined #openttd
21:34:53 <Wolf01> Also I want helicoidal gears
21:42:50 <andythenorth> 1 commit is all it takes
21:53:36 <peter1138> Hmm, how do you get the sprite aligner up?
21:55:34 <peter1138> Gotta enable it in the config. Done now.
21:55:47 <peter1138> So I have a patch here to add zoom in/out buttons :p
21:59:17 <peter1138> Not that it applies of course.
21:59:41 <peter1138> It's only 4 years old though.
22:05:05 <peter1138> Heh, the old patches to scale images differently.
22:08:51 <andythenorth> let's not though :)
22:09:03 <peter1138> It's pre-32bpp-grfs.
22:09:14 <andythenorth> it's uncanny valley
22:09:17 <andythenorth> it's nearly brilliant
22:12:34 <andythenorth> it's like a tour of all the things we can't have :)
22:12:59 <Wolf01> Devs are mean, I leave :(
22:13:32 <peter1138> That's not actually Pikka...
22:13:49 <glx> cosmetic work needed tor the half rivers
22:16:19 <peter1138> I spent time doing that at some point... why...
22:16:41 <andythenorth> Wolf01: bad community
22:16:55 <andythenorth> i drew the half-rivers :P
22:16:59 <andythenorth> then I rage quit
22:17:14 <andythenorth> peter1138: 'because you could' :P
22:38:28 <__ln__> maybe you should divide it by 8
22:39:05 <LordAro> maybe take the natural log of 8
22:39:52 *** Wacko1976 has joined #openttd
22:43:13 <peter1138> Hmm, where did I leave my tablet...
23:15:27 *** andythenorth has left #openttd
23:23:11 *** sim-al2 has joined #openttd
23:40:12 *** Thedarkb has joined #openttd
continue to next day ⏵
