For this I actually use two generic Lists and as the objects are processed, the ones that aren't finished yet (the black ones) get pushed into the other list. 'Finalized' pixels are removed from the List as they don't need to processed anymore. Each frame all of those instances are advanced one iteration and the colors in the images color array are updated if a pixel has 'escaped'. It also holds the iteration count (integer) and a few other things. It uses a class instance for each pixel in the image that holds the complex number(two double values) of the position in the image as well as the current iterated position. So you may need to use a pool if the performance is too bad.Īs an example I always like to reference my crazy parallel mandelbrot renderer. Of course instantiating 10k objects is kinda slow. If it's a class, it depends on how you now handle your grid. If it's a struct with 'too much data' (more than the max recommended 16 bytes) performance goes downhill. However it does matter when it comes to performance issues. It doesn't matter for the general question. You said that the type of 'T' doesn't matter and that's true. Navigating a flattened array is usually the fastest way to process a grid of anything. Also the Dictionary would need to expand its internal structure as it grows which can introduce huge spikes, especially when you start with an empty dictionary and no capacity reserve. Reading and writing an array element is also an O(1) operation but is much faster. Though it doesn't tell you much about the actual performance. However BigO is just about how the performance scales with growing number of elements and it stays constant.

Note that using a Dictionary to represent your field is probably the worst datastructure you could choose A lot people get fooled by the O(1) complexity. That way limiting factor isn't area but the amount of lines/corners created which is equal to player keypress count. But you can also replace the 'filling' part and checking when you hit a wall based on polygons with no cells at all. Doing polygon based side check like Bunny suggested is one step of it. Although that would be a bit more trickier to implement, than cell based approach.

If the area really is so big that processing all the cells takes too long there is possibility to completely switch away from cell based approach and operate purely with polygons. Proper solution is to plan for the worst case. And if flood filling wrong side is too slow, the time to fill correct side (size of half game are) will be on the same order of magnitude which is too slow. In the worst case player could still split the whole game field in half forcing you to flood fill half of it. Having a fast check for quickly choosing which half to fill only helps in the good cases. Although i would expect that you are doing some additional things incorrectly for performance to be a problem. The fact that you are using Dictionary instead simply 2d array doesn't help. How big exactly is your actual game field? With a clean C++ implementation even 10^6 should be doable many times times per second, and 10^4 should be doable even with C# and mono. Any ideas would be appreciated.įlood filling 10^4 cells shouldn't really be a problem for modern computer even an older laptop, unless you have implementing it incorrectly making it quadratic or worse, or you are using some inappropriate functions which cause huge overhead. It doesn't have to get the most efficient path (like with A* pathfinding), just check if it's connected at all. The grid data is stored in a Dictionary, where T is unimportant. Basically, quickly check if there's a free path from one to the other. What I want to know is if there's a performant way to check if a single cell on one side of the player's path is connected to the cell position of the Qix. While it runs ok on my PC, it delays quite a bit on a laptop. The current floodfill algorithm simply queues neighboring cells, as long as they are free, and checks each cell as it goes to make sure it's not the Qix. This seems inefficient, as sometimes it checks upward of 12,000 cells before it finally finds the Qix. There are a lot of cells and sometimes the performance impact of the flood fill is costly, especially if the Qix is far away from the player and the first flood fill check happens to be the side the Qix is on. If it encounters the Qix, it attempts to fill the other side. When the player completes an area, it starts a flood fill on one side of the path the player made. I'm making a game like the old game Qix (like splix.io).

Splix io edit