Template library for common functionality

longPtrCall commented 1 month ago

Describe the project you are working on

Simple 2D games for internal companies.

Describe the problem or limitation you are having in your project

GDScript lacks of something like c++ STL library. I am currently working on a project that needs something like linked list. Implementing a forward list is not a big deal, but it took me an hour. And there are many common 'template' problems like this.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Implementing a template library will save time for game developers who choose Godot and GDScript over other options. Although this can potentially increase performance in final projects (solutions that powered by Godot) as these functions will be solved once (either by professional developers or community), they will have same or higher performance anyway, comparing to implementations made by developers (who uses Godot).

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Standard template methods and classes are accessible through GDScript.

If this enhancement will not be used often, can it be worked around with a few lines of script?

This library can be a module (please see section below).

Is there a reason why this should be core and not an add-on in the asset library?

This library (a collection of classes and functions) can be either a native asset or be a built-in. There are some pros and cons in both cases:

Making it a built-in solution will result in lower space consumption (as compiling a shared library requires about 2 megabytes of glue code) and allows to improve GDScript functionality more 'official' way. But most of the functionality will not be used and will just waste the space (redundant code).
Making a separate addon feels like a 'nightly' solution, but still a good option anyway. As I mentioned, creating an addon will require an additional glue code, which will take even more space than the library itself.

Meorge commented 1 month ago

I am currently working on a project that needs something like linked list. Implementing a forward list is not a big deal, but it took me an hour. And there are many common 'template' problems like this.

Sorry if this has an obvious answer, and it's just not occurring to me right now, but wouldn't the standard Array be what you're looking for here?

sockeye-d commented 1 month ago

This is infeasible because the current code for generics is really specific and would be hard to apply beyond the Arrays and Dictionaries it's currently implemented in (at least, this is my understanding of it, if it's wrong please correct me). Once GDScript gets proper generic support (with supporting GDExtension as well) it should be trivial to create such an addon or engine module

longPtrCall commented 1 month ago

I'm sorry for any misunderstanding. I am not talking about C++ templates (aka Java generics). I mean, there must be standardized classes and functions for general cases, which are not used in the engine, but often used during software development using Godot.

When it comes to generic types, I think, Variant is powerful enough. Of course, to make generic types more powerful, GDScript must support interfaces (I saw people are already discussing this in proposals).

The goal of this issue is to define, how this library should be implemented. Making it a built-in option will result in GDScript support more official way, giving some useful tolls for specific problems, while making this library as the asset will have exactly the same effect, but unofficially (please refer to issue description message).

longPtrCall commented 1 month ago

I am currently working on a project that needs something like linked list. Implementing a forward list is not a big deal, but it took me an hour. And there are many common 'template' problems like this.

Sorry if this has an obvious answer, and it's just not occurring to me right now, but wouldn't the standard Array be what you're looking for here?

Thank you for replying. My case is not a problem at all. I was needed exactly in linked list. Unfortunately, arrays are not match with my tasks requirements and playing around them will lead to inefficient garbage code. I already made the implementation of this structure using GDScript. I just wonder, why GDScript has no built-in support for this type, alongside many other types and functions other languages have.

Meorge commented 1 month ago

I think I'm still having trouble understanding exactly what you're looking for and how/why the current solutions in GDScript aren't sufficient.

For engine development and C++ code itself, Godot has its own container classes, including Vector and List. As for a linked list in GDScript, that is what a typed Array would be for. It has methods such as push_back to add an element to the end, push_front to add an element to the beginning, and insert to add an element in the middle.

var arr: Array[int] = []

arr.push_back(1)
arr.push_back(2)
arr.push_back(3)
arr.push_front(0)
arr.push_back(5)
arr.insert(4, 4)

print(arr)  # should print [0, 1, 2, 3, 4, 5]

longPtrCall commented 1 month ago

I think I'm still having trouble understanding exactly what you're looking for and how/why the current solutions in GDScript aren't sufficient.

For engine development and C++ code itself, Godot has its own container classes, including Vector and List. As for a linked list in GDScript, that is what a typed Array would be for. It has methods such as push_back to add an element to the end, push_front to add an element to the beginning, and insert to add an element in the middle.
var arr: Array[int] = []

arr.push_back(1)
arr.push_back(2)
arr.push_back(3)
arr.push_front(0)
arr.push_back(5)
arr.insert(4, 4)

print(arr)  # should print [0, 1, 2, 3, 4, 5]

In my case I could use arrays by the way, if only I were not blind and read the docs. I just messed it with python arrays. But there are many other classes and functions (like tuples, idk). I think I should use arrays instead (after making sure they actually have constant time insertions and remove operations), but the term Array sounds kinda suspicious there.

Meorge commented 1 month ago

I think I should use arrays instead (after making sure they actually have constant time insertions and remove operations)

Sounds like they may be O(n). From the docs for insert:

Note: Every element's index after position needs to be shifted forward, which may have a noticeable performance cost, especially on larger arrays.

That being said, it's probably still best to start with Godot's built-in Array type and verify that your use case has actual performance issues before worrying about switching to a new data structure. I've been surprised and impressed with GDScript performance; things that I thought would be big performance bottlenecks have mostly been fine in practice.

longPtrCall commented 1 month ago

I think I should use arrays instead (after making sure they actually have constant time insertions and remove operations)

Sounds like they may be O(n). From the docs for insert:

Note: Every element's index after position needs to be shifted forward, which may have a noticeable performance cost, especially on larger arrays.

That being said, it's probably still best to start with Godot's built-in Array type and verify that your use case has actual performance issues before worrying about switching to a new data structure. I've been surprised and impressed with GDScript performance; things that I thought would be big performance bottlenecks have mostly been fine in practice.

Oh, that's it. I need an array with constant time insertions. I still need to implement a linked list. And just as I said, this issue is not about containers, it's about a collection of different classes and methods for daily use. I think it could be just bindings for C++ STL with Variant or something. It should be accessible through GDScript.

girng commented 4 weeks ago

hmm interesting idea. however, if the developer needs to use those kinds of containers in the STL wouldn't they be better off just having their own custom c++ module?

if a module does get created for it, could be added to https://github.com/godotengine/awesome-godot

longPtrCall commented 4 weeks ago

hmm interesting idea. however, if the developer needs to use those kinds of containers in the STL wouldn't they be better off just having their own custom c++ module?

if a module does get created for it, could be added to https://github.com/godotengine/awesome-godot

Thank you for commenting this out! This issue persists to decide how this functionality should be added. As I mentioned, it can be either a native module or a built-in collection. Once I have an answer, I can even contribute (and I am going to; after solving my primary tasks). It seems like everybody sees it as an asset. If so, it will be an asset. I will wait for about a month before I start resolving this issue.

godotengine / godot-proposals