Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

AI can effectively hang OpenTTD by sorting a very large array. #4830

Closed
DorpsGek opened this issue Nov 8, 2011 · 1 comment
Closed

AI can effectively hang OpenTTD by sorting a very large array. #4830

DorpsGek opened this issue Nov 8, 2011 · 1 comment
Labels
component: AI/Game script (squirrel) This issue is related to Squirrel (Scripting language) flyspray This issue is imported from FlySpray (https://bugs.openttd.org/)

Comments

@DorpsGek
Copy link
Member

DorpsGek commented Nov 8, 2011

Yexo opened the ticket and wrote:

Example: savegame from this post: http://www.tt-forums.net/viewtopic.php?f=31&t=57296

An AI calls sort() on an array with 50000 elements. This runs squirrels builtin function _qsort (found in sqbaselib.cpp). Since quicksort is worst-case O(N**2) this quickly takes too long.

OpenTTD cannot suspend in the middle of the _qsort call. One possible solution is to disable the builtin sort() function and write a comparable one in squirrel which can be suspended. Downside of this approach is that it'll hurt performance. A more complication solution is to limit the builtin function in size, and write a wrapper that splits the input and calls the builtin function.

Reported version: Version?
Operating system: All


This issue was imported from FlySpray: https://bugs.openttd.org/task/4830
@DorpsGek
Copy link
Member Author

Yexo closed the ticket.

Reason for closing: Fixed

In r23186


This comment was imported from FlySpray: https://bugs.openttd.org/task/4830

@DorpsGek DorpsGek added flyspray This issue is imported from FlySpray (https://bugs.openttd.org/) bug component: AI/Game script (squirrel) This issue is related to Squirrel (Scripting language) labels Apr 7, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
component: AI/Game script (squirrel) This issue is related to Squirrel (Scripting language) flyspray This issue is imported from FlySpray (https://bugs.openttd.org/)
Projects
None yet
Development

No branches or pull requests

1 participant