Config
Log for #openttd.dev on 15th November 2013:
Times are UTC Toggle Colours
00:11:06  *** frosch123 has quit IRC
00:13:46  *** tycoondemon has quit IRC
00:14:01  *** tycoondemon has joined #openttd.dev
00:16:22  *** zydeco has quit IRC
02:24:39  *** LordAro has quit IRC
08:00:39  *** adf88 has joined #openttd.dev
08:00:39  *** ChanServ sets mode: +v adf88
08:18:46  *** adf88 has quit IRC
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
09:22:33  *** Supercheese has quit IRC
11:50:56  *** Lord_Aro has joined #openttd.dev
11:50:56  *** LordAro has quit IRC
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
14:05:24  *** adf88 has quit IRC
15:15:18  *** adf88 has joined #openttd.dev
15:15:18  *** ChanServ sets mode: +v adf88
16:23:06  *** adf88 has quit IRC
17:22:06  *** juanjo_ has joined #openttd.dev
17:42:41  <frosch123> @voice juanjo_
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:48:11  <peter1138> ok
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:57:22  <frosch123> feel free :)
17:58:12  <juanjo_> In the comment added about catchment areas it is stated that they are different due to performance decisions.
17:58:37  <planetmaker> yes, basically
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:05  <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:39  <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:17:51  <adf88> So it's a bitmap...
18:17:58  <adf88> maybe a sparse tree
18:17:59  <adf88> ?
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:18:11  <frosch123> https://github.com/JJ-OpenTTD/openttd-cargodist/commit/3a597b30e2a8f577b27e7fc40e293761682a3222 <- that one?
18:19:58  <juanjo_> No, that's for seeing the catchment area. That comes later. I'm looking for it...
18:21:01  <juanjo_> It's this one and later commits: https://github.com/JJ-OpenTTD/openttd-cargodist/commit/3cc526d945a7d67cb14d195484a417be4f481e33
18:21:23  <LordAro> needs some coding style stuffs
18:21:36  <frosch123> LordAro: not now
18:21:44  <LordAro> :p
18:21:52  * LordAro blames Alberth
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:24:11  <LordAro> :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:45  <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:31:58  <juanjo_> I hate oilrigs
18:32:13  <frosch123> so for industry->station transfer it should also use the new algorithm
18:32:15  <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:34:39  <juanjo_> I also add that cached list: https://github.com/JJ-OpenTTD/openttd-cargodist/commit/9de68027ebde7abbeaa943e9fe5b2bb2c4e2c06dรง
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:01  <Rubidium> isn't there a bitset or so in stl?
18:45:13  <frosch123> yes, std::set<boolean> is specialised
18:45:14  *** DorpsGek changes topic to "OpenTTD Dev Channel || Latest SVN: r26004 || Logs: http://webster.openttdcoop.org/?channel=openttd.dev || Voice (talk-right) upon request via #openttd; make sure you are registered to NickServ before asking"
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  <Rubidium> yup
18:50:42  <frosch123> maybe bitset is vector-ish
18:51:13  <Rubidium> nope, there's a bit_vector/vector<bool>
18:51:34  <Rubidium> http://www.sgi.com/tech/stl/bitset.html
18:51:39  <LordAro> or, http://en.cppreference.com/w/cpp/container/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:52:41  <frosch123> i think so
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.
18:54:41  <juanjo_> Bye
18:55:01  *** juanjo_ has quit IRC
19:55:07  *** Alberth has left #openttd.dev
20:32:38  *** zydeco has joined #openttd.dev
20:37:10  *** Supercheese has joined #openttd.dev
21:03:10  <Rubidium> http://rbijker.net/openttd/fs5478.diff <- I hope that works as a fix for the problem; not that I really found a problem with the current code, but this design might be more resilient
21:06:00  <frosch123> +			mutex->WaitForSignal(); <- + this->
21:12:12  <frosch123> doesn't look wrong
22:22:03  *** DorpsGek changes topic to "OpenTTD Dev Channel || Latest SVN: r26005 || Logs: http://webster.openttdcoop.org/?channel=openttd.dev || Voice (talk-right) upon request via #openttd; make sure you are registered to NickServ before asking"
23:21:23  *** frosch123 has quit IRC
23:23:34  *** adf88 has quit IRC

Powered by YARRSTE version: svn-trunk