Dataflow programming in roguelikes, exploring Field of view calculation

[Omnivore]

As a final, from my perspective anyhow, follow up to this topic;

TLDR; The data flow model and parallel processing in general is currently a poor fit for roguelike games.

Roguelike 2D field of view calculations on modern hardware are so cheap that you can get away with just about anything unless you're targeting androids or iphones.  I finally realized how silly it was when my benchmarks showed < 250 *micro* seconds   Similar results are seen with any decent pathfinding implementation.

The larger question for me, was data flow programming's applicability to roguelikes, and indeed the entire parallel processing subject where roguelikes are concerned.  For fine grained parallelism, unless you're planning to run your roguelike on CUDA cores, you will see a *massive* slowdown.  A rule of thumb breakpoint seems to be around 100K instructions, less than that and the cost of synchronization and context swapping will cost more than the calculations.  Above that you start seeing some improvements but until you get significantly higher its not, in my opinion, worth the hassle and added bugs.

If your game encounters performance issues, it may be worth the effort in larger games to separate the model and view into their own threads/processes unless you have a lot of crosstalk between them.  From what I'm seeing in tests, the only other scenario where it may make sense is if you use a client server model with each mob being a pseudo client.  This is basically the Actor model taken to a process rather than concurrent threading model.  Of course, concurrency is not parallelism, so you may find uses for concurrency even where parallel gains no benefit or even incurs extra costs.

PS: For some reason I am now tempted to write a massively parallel roguelike using CUDA that runs on your graphics card and displays in a telnet terminal

[Krice]

I was looking at the speed of Kaduria's FOV, it seems to be average of 8ms in 35x35 area, but I think it can be faster with changing the priority in LOS check routine which is new one since the refactoring of map routines. It's a single thread routine. That 8ms includes drawing tiles, in other words the entire map display routine. But I think it doesn't yet include lighting, I'm not sure. Besides I'm probably going to rewrite lighting routines as well.

[Krice]

After fixing a bug where I was accidentally passing target list as value in tile drawing routine I've now found out that FOV is anything from 2 to 10ms with reset of static light map (dynamic lights not yet functional). I think it's quite good (and this is before the planned optimization in priority of checking FOV hits (walls should be check first)). Although the visible area is 17x17 rectangle of course, with circular 35x35 total area.

[Xecutor]

Code: [Select]

D:13:51:36 timer.fov :fov time=110237ns
D:13:51:36 timer.ligh:light update=493345ns

Fov has radius 15 and is done on boundless map. i.e. Access to each tile includes hash lookup.
Light update includes scan of screen area(80x40) +- max light radius (which is again 15) = 110x70
for each light source fov is calculated. There are several light sources(6 mb?) in the area.
Running this on mac mini with 2,3 GHz Intel Core i7

[Krice]

I can't make anything out of that. Is that FOV 110ms in ms's? How it can be that slow? Btw, my computer has old Pentium dual core E5500 2,8Ghz processor which is good, because if it's fast in that it's super fast in newer computers.

[Omnivore]

110237ns = 110usec(microseconds) = 0.11 msec.  The interesting part of being able to hit speeds like that with FOV calcs is that you can now afford to composite them.  Depending upon your language of implementation, you may still not want to give every mobile its own FOV calc, but you can at the very least add peek at corner, additional light sources, etc.  It also means that you have a larger time budget to spend on things like sound maps, influence maps, more interesting AI, etc.

Earlier in this thread I kinda gave Data Flow Programming (DFP) the short shaft.  Yes it is true it will not give you performance gains through parallelism at these levels, however, modeling your algorithms in DFP can help you to improve your code quality and hence lower maintenance costs.  For me at least, I also found that decomposing algorithms into pipelines and nodes let me more easily spot alternative solutions. 

[Krice]

If I check only FOV routine I get constant 1ms times, don't know how accurate it is, because the resolution of the timer is 1ms. So yes, that's easy. On top of that you have 20 times faster processor and at least 5 times faster OS (I have Windows 7). So you have 5 x 20 = 100 times faster hardware.