How to instantiate thousands of clickable polygons: optimizing or choosing a new approach ?

Question

I am working on an strategy game where the map is generated as a Voronoi diagram : each province is a Voronoi cell. To achieve this I used the Delaunator library with the VoronoiHelper, thanks to the guidance of @Thomas Karcher. Currently, a generated map looks like this, or like this if I put a smaller amount of polygons.

The issue I'm now facing is performance : with a map of the size of the first screenshot, with 6000 polygons, there's 10fps when zoomed-out and a considerable zoom-in is needed to approach 60fps.

In brief, my approach is for now to generate the map by adding for each cell a MapRegion scene composed of a Polygon2D and a CollisionPolygon2D, the root node of the MapRegion.tscn being an Area2D. I've read that adding thousands of scenes may cause lag, which is understandable, but I have no idea to do it without. Is there any convenient way to do such a thing without scenes ?

I also thought that I could optimize the project while keeping my approach, but GLES2 doesn't seem to make thing faster and my code is pretty empty as soon as the main scene is generated - for instance my _process() function only have a camera zoom and moving feature, nothing more.

Any idea of new approach or optimizing advice will be highly appreciated, thanks for reading :)

Comments

Just adding a comment so I can clarify something:

Do you really need all those polygons as collision shapes? Can't you just have one collision shape to rule them all (basically a large rectangle), then, when the user clicks, find the correct province underneath the mouse?

---

It would make the process depend on polygons areas, which wouldn't be convenient to implement. Nonetheless, I'm now curious about how to do it, so if you have an idea, go ahea! - but it needs to be quite flexible because of the procedural nature of the whole thing

---

Well, let me ask one more clarifying question: if you do not include the CollisionShapes at all, do you get the severe lag at higher resolutions? Because if so, it would require an entirely different approach from the polygon method itself, regardless of how clicks are detected.

---

I've tested without the CollisionShapes, as you suggested, and it is still low when there's a thousand polygons or more - it doesn't seem to change anything. As you do, I think that maybe a different approach would be necessary.

That being said, I'm still curious about possible optimizations, even if I guess that it would not be enough.

Thank you very much about for your help @Kyle Szklenski ! :)

---

Rats! (Regarding missing collision shapes - I had a few ideas to handle selection.)

I'm just thinking out loud here, don't necessarily know any answers for sure, but I would think for such a massive number of polygons, the most natural place to build them would be on the GPU directly. That means tapping into shaders instead of relying on nodes directly. There's also the possibility of finding a C++ library that can be compiled into the engine, but I do not know of which one would work offhand.

So my ultimate suggestion - for now - just to get something that maybe isn't so slow - would be instead of using draw calls or creating polygon nodes and pushing them into the scene tree, try creating a shader that draws the polygons out for you. If that speeds it up on your computer, then we can discuss how to find where clicks occur inside them.

---

I'll look for this, althought my Godot skills should not be enough to implement the whole thing by my own. I'll reach you if I achieve anything, thanks again for you dedication ;)

Answer 1

I guess you're using Godot 3.2.3 or older? There was a batching issue in these versions, which was fixed just a couple of week ago: https://github.com/godotengine/godot/pull/42119 . I compared polygon performance between 3.2.3 und 3.2.4 Beta 3 and immediately saw a performance increase. But yes, if you can decrease the number of nodes, this will also help regardless of the version you're using.

So I'd suggest the following changes:

1) Run your project in the latest version of Godot (currently 3.2.4 Beta 3).
2) Instead of thousands of Area2D, manually create just one in your scene tree ("ClickableMap")
3) In your ready function, add all CollisionShapes to this Area2D, and send all polygons to the VisualServer directly (without instancing Polygon2Ds any more):

---

for cell in cells:
    var coll = CollisionPolygon2D.new()
    coll.set_polygon (cell)
    $ClickableMap.add_child (coll)
    var item = VisualServer.canvas_item_create()
    VisualServer.canvas_item_set_parent(item, get_canvas_item())
    VisualServer.canvas_item_add_polygon(item, cell, [Color(randf(), randf(), randf())])

---

4) Connect the input_event signal of ClickableMap and use the shape ID to check which region was clicked:

---

func _on_ClickableMap_input_event(_viewport, event, shape_idx):
    if event is InputEventMouseButton and event.pressed:
        if event.button_index == 1:
            print ("Region #" + str(shape_idx) + " was selected.")

---

This should be enough to raise the performance back to reasonable framerates.

Comments

I was using 3.2.3, yes. Again, you solved it all ! Hahahaha
With my 6000 polygons example project, the fps just doubled or maybe tripled. I tried your scripts and it all work well, but now I just need to find a new way to fix the eternal borders problem. I'll then compare fps for the different approaches, even if the old approach you propose in the previous post seems to work now well with the update.

Thank you very much Thomas, I am really grateful for the time you took :)