IRC logs for #openttd.dev on OFTC at 2013-11-15
⏴ go to previous day
00:14:01 *** tycoondemon has joined #openttd.dev
08:00:39 *** adf88 has joined #openttd.dev
08:00:39 *** ChanServ sets mode: +v adf88
08:21:44 *** adf88 has joined #openttd.dev
08:21:44 *** ChanServ sets mode: +v adf88
08:54:53 *** Alberth has joined #openttd.dev
08:54:53 *** ChanServ sets mode: +v Alberth
09:03:18 *** LordAro has joined #openttd.dev
09:03:18 *** ChanServ sets mode: +v LordAro
11:50:55 *** Lord_Aro has joined #openttd.dev
11:51:43 *** Lord_Aro is now known as LordAro
11:52:05 *** ChanServ sets mode: +v LordAro
12:14:30 *** frosch123 has joined #openttd.dev
12:14:30 *** ChanServ sets mode: +v frosch123
15:15:18 *** adf88 has joined #openttd.dev
15:15:18 *** ChanServ sets mode: +v adf88
17:22:06 *** juanjo_ has joined #openttd.dev
17:42:41 *** DorpsGek sets mode: +v juanjo_
17:43:04 <frosch123> if you have registered to nickserv, you can bother pm to give you permanent voice
17:48:10 *** peter1138 has joined #openttd.dev
17:48:10 *** ChanServ sets mode: +v peter1138
17:49:51 *** adf88 has joined #openttd.dev
17:49:51 *** ChanServ sets mode: +v adf88
17:56:20 <juanjo_> Hi! I would like to comment about r25998.
17:58:12 <juanjo_> In the comment added about catchment areas it is stated that they are different due to performance decisions.
17:59:54 <juanjo_> I tried with the last option: change the search from stations and use the tiles of stations.
18:00:11 <juanjo_> The implementation I did was not the best possible
18:01:34 <juanjo_> But as I cached the catchment area, although the cost of calculating it is quite high, I barely noticed performance problems
18:01:51 <frosch123> how did you cache it?
18:01:56 <frosch123> some set of tiles per station?
18:02:04 <planetmaker> can you prove your 'barely notice' by profiling data?
18:03:18 <juanjo_> I don't know how to profile data. Sorry.
18:03:22 <planetmaker> I actually haven't seen any for any solutions to that issue, even the one disregarded with the reasoning given
18:04:29 <juanjo_> Anyway, as I can't give profiling data, I'll try to explain it another way.
18:05:57 <juanjo_> The cost of calculating a catchment area considering each tile of the station is high, but you only need to calculate that when you load a game or when you add/delete parts of a station
18:07:31 <planetmaker> the area: yes. Acceptance: no
18:07:38 <planetmaker> you need to check that every time
18:08:53 <frosch123> that's what i asked: did you add some list of tiles to stations?
18:09:03 <frosch123> which contains the tiles in the catchment area without duplicated?
18:09:17 <frosch123> did you also do that for industries? (which also have non-rectangular shapes)
18:11:20 <juanjo_> For each station there is a global tile area, which includes all tiles that could fall inside station's catchment.
18:11:54 <juanjo_> Then I also store an array for referencing each tile of the tile area.
18:12:58 <juanjo_> The array is a bit array, each bit representing each one of the tiles, in the same order as TILE_AREA_LOOP.
18:13:26 <juanjo_> Let me put it with an example
18:16:13 <juanjo_> I have a station with two tiles t1=25634, t2=2335346. I build the rectangle containing those two tiles. Then I expand it, with a convenient radius, as some tiles that will be serviced will fall outside the rectangle
18:18:09 <juanjo_> Once I have the tile area of all tiles that can fall into station's catchment (let's say it is a 20x30 tilearea), I allocate 20x30 bits...
18:19:58 <juanjo_> No, that's for seeing the catchment area. That comes later. I'm looking for it...
18:21:23 <LordAro> needs some coding style stuffs
18:22:00 <frosch123> stop the code style trolling
18:22:13 <frosch123> it's the algorithm that matters
18:22:41 <juanjo_> While you complain about coding style and not about the implementation, I'm okay with it :P
18:27:33 <juanjo_> Finally, the algorithm fills in the 20x30 array, so you keep the list of "serviced tiles", used when doing tile area loops
18:28:36 <frosch123> oh, you are using bool*
18:28:44 <frosch123> i guess you can use TileIndex* then as well
18:29:04 <frosch123> do you have an estimate how many memory that needs in a normal game?
18:29:22 <frosch123> hmm, how many stations are there in an average game?
18:29:40 <frosch123> maybe depends whether busstops are used
18:30:12 <juanjo_> What is the maximum distance between two tiles of the same station? 64?
18:30:39 <frosch123> hmm, 1000 busstops with 81 catchment tiles each, would be less than 400k, so i guess no issue at all
18:30:55 <frosch123> yeah, max stations spread is 64
18:31:02 <frosch123> anyway, looks like memory is no concern
18:31:14 <frosch123> so, one could cache the tiles in the catchment area per station and per industry
18:31:31 <frosch123> and even add a switch to use the traditional catchment area for savegame compatibility
18:31:33 <juanjo_> per industry is not needed
18:31:38 <frosch123> btw. i like the oilrig thingie :p
18:31:56 <frosch123> industries also have non-rectangular shapes
18:32:13 <frosch123> so for industry->station transfer it should also use the new algorithm
18:32:16 <juanjo_> i store just their footprint
18:32:52 <frosch123> luckily houses are only rectangular :p
18:33:09 <juanjo_> Just check which tiles of industry footprint are "serviced" by a station
18:33:51 <frosch123> hmm, we already have a list of stations per industry, right?
18:34:04 <frosch123> or was it the other way around
18:43:51 <juanjo_> About the memory it requires, I'm not an expert to say it is not so much. Biggest station possible requires about 5k bits... There are lots of other issues. I just did the implementation and it worked. I didn't cared to make things more efficient.
18:44:44 <frosch123> mind that boolean is usually 4 bytes, not 1 bit
18:45:00 <Rubidium> isn't there a bitset or so in stl?
18:45:13 <frosch123> yes, std::set<boolean> is specialised
18:46:57 <juanjo_> I'll look into it and rewrite it. Hope it is not a big deal.
18:48:39 <Rubidium> there's bitset, but that's not really a proper set and has a compile time size. I reckon it's the fastest though
18:49:41 <frosch123> you mean a fixed size bitset for 64x64 + biggest catchment radius?
18:49:59 <frosch123> i guess an ordered set is good enough
18:50:00 <Rubidium> if you want to use bitset, then yet
18:50:15 <frosch123> and actually, since you only want to do inclusion tests fast, and not insert/delete
18:50:21 <frosch123> it could even be an ordered vector
18:50:41 <frosch123> maybe bitset is vector-ish
18:51:13 <Rubidium> nope, there's a bit_vector/vector<bool>
18:51:55 <frosch123> oh, right, std::Vector<bool> was specialised, not std::set<bool> :/
18:52:36 <Rubidium> so vector<bool> would be the 'right' one to use?
18:53:05 <LordAro> according to documentation
18:54:30 <juanjo_> Well, I have to go. If you find more issues or any other idea, please let me know.
19:55:06 *** Alberth has left #openttd.dev
20:32:38 *** zydeco has joined #openttd.dev
20:37:10 *** Supercheese has joined #openttd.dev
21:06:00 <frosch123> + mutex->WaitForSignal(); <- + this->
continue to next day ⏵