Spatial Display and asynchronous updates for desktop Gui app
Okay, so we need to display a set of possibly moving objects in 2D on a top-down map.
As well as do hit-detection of the cursor against those entities.
Naturally, we need to draw them.
So we have a need to be able to quickly obtain a slice of them that intersect the viewbox of the 2D map, as well as detect which ones we are clicking on.
So, spatial-indexing is desired, hence the thought to have a QuadTree to organize them.
This would not be a thread-safe collection, and we would need to synchronize access to it.
Updates to this would come in from threads other than the main thread.
The main thread needs to read from the tree very often.
Which of the folowing approaches would be preferred:
1) Assert that the tree is a threaded object local to the main thread, thus any updates to the tree will be dispatched and executed on the main thread.
2) Have access to the QuadTree guarded through the use of reader writer locks, with threads contesting and taking these locks when needed.
I am very open to discussion and ideas about this - perhaps some of my assumptions here are wrong. :catfine:
22 Replies
the best possible performance, would probably be to batch update + possible polling for changes made on/by other threads
How would you batch updates?
if you are updating your UI via bindings, then its just a matter of keeping a concurrentdictionary of propertychangedargs + the thing that raised them around
This is probably not being done by bindings, no.
i'd probably try using DTOs then
a DTO would represent a set of changes that need to be made to a certain object
Suppose for instance, we're receiving updates asynchronously through messaging - RabbitMQ-AMQP.
and then you can either take that DTO, remove it from some queue, or just get a copy and apply that where required
Perhaps I could use a shared ConcurrentQueue of sorts?
it really depends on if you want to be able to merge DTOs that are meant for the same entity and whether the entity needs to see every change that happened
Hmm, yeah - each message is an entire state-snapshot for a single-entity - a later-message supersedes a previous one.
nice, that makes it easier
I wonder how I might ensure I only reindex an entity in the tree once if it's had multiple updates in the last frame.
i'd want to avoid having that problem. is that an actual requirement?
No, I could just ignore it - but reindexing an entity in the tree would be a removal and an insertion.
maybe build a flat (persistant?) datastructure, that your tree can consume? updating a flat list is faster than updating a tree
e.g. a dictionary, where the path in your tree is the key perhaps
Well, part of the reason I want a tree is to speed up the query for
"I want to find the entities within the viewbox of the gui"
im not saying you should abandon the tree
im saying build an other abstraction for updating it
Even if we have 10000 entities?
Okay you got me confused for a moment there.
sorry, i often forget negations when chatting
anyway, 10k entries in a dictionary should be fine
even if its concurrent
Hrmm... I'm not sure I understand what you mean by a path in the tree as a key.
well, in my imagination, every node in the tree is unique
meaning that to get to every leaf on every node, there is a as unique "path" of nodes to follow to get there, from the root of the tree
imagine a file path on the filesystem
folders are nodes and leafs, while files are only leafs
that obviously falls apart, if your nodes are not unique
Well, hrmm, not really how I thought of the quadtree.