algorithms
Use when a Godot game needs paths for many agents at once, fleeing, connected regions, prerequisites that must not loop, a stable per-frame sort, "did you mean" suggestions or an exact puzzle solver, or when about to copy an algorithm from a public repository or textbook.
- License 许可
- Apache-2.0
- 最近更新
- 2026-11-13
- Stars
- ★ 1
- Forks
- 0
01 前言 Front Matter
- name
- algorithms
- description
- Use when a Godot game needs paths for many agents at once, fleeing, connected regions, prerequisites that must not loop, a stable per-frame sort, "did you mean" suggestions or an exact puzzle solver, or when about to copy an algorithm from a public repository or textbook.
03 SKILL.md 正文
Algorithms for games (Godot 4.7, C#)
Godot's built-ins first, .NET's second, and a small tested helper for each gap. The textbook version of an algorithm is
written to be read, not to run sixty times a second: the measurements below (.NET 8, Godot 4.7.2, 4 cores, Linux) are
of TheAlgorithms/C-Sharp's implementations against the helpers in
${CLAUDE_PLUGIN_ROOT}/examples/csharp/src/Example.Core/ (tests: tests/Example.Core.Tests/AlgorithmsTests.cs).
1. Licence before code
- TheAlgorithms/C-Sharp is GPL-3.0. Pasting any of it into a game makes the whole game GPL: its source must go to every
player, and console stores and most publishers refuse it (
creditsrefuses the GPL family,asset-pipeline). Read it to learn the idea, close it, then write and test your own. - Its explanations (TheAlgorithms/Algorithms-Explanation) are MIT. Stack Overflow answers are CC BY-SA (credit, and
share-alike for the snippet); Rosetta Code is GFDL. Record anything kept in
assets.json(asset-pipeline).
2. What to use
| Problem | Use | Note |
|---|---|---|
| One agent's path on a grid | AStarGrid2D (Region, Update(), SetPointSolid, GetIdPath) |
0.65 ms a query on 128 x 128 with 20% walls |
| Paths on a graph of rooms or waypoints | AStar2D / AStar3D |
|
| Free movement on a mesh | NavigationAgent2D / 3D |
game-ai section 7 |
| Many agents toward one target, or each to its nearest of several | DistanceField (a Dijkstra map) |
200 agents: 131 ms with AStarGrid2D, 1.9 ms with one field |
| Running away without backing into the nearest corner | DistanceField.Flee() |
|
| Is every room reachable; islands; the largest cave | Regions.Label |
|
| Joining as you go (Kruskal maze, match-3 clusters, merging islands) | DisjointSet |
|
| Prerequisites that must not loop (tech tree, quests, recipes) | the data runner's acyclic (section 5) |
|
| The next event by time, an open set | PriorityQueue<TElement, TPriority> |
no decrease-key: enqueue again, skip stale entries |
| Shuffle, draw without streaks | ShuffleBag (Procgen/Draws.cs), Fisher-Yates on DeterministicRandom |
never OrderBy(_ => rng.Next()) |
| Triangulate, hull, point in polygon | Geometry2D.TriangulateDelaunay, ConvexHull, IsPointInPolygon |
|
| "Did you mean" for a console, cheat or mod id | Suggest.Closest |
String.Similarity scores "jmup" against "jump" as 0 |
| Draw or turn order sorted every frame | insertion sort over last frame's order | section 3 |
3. Traps in textbook code (measured)
- Recursion on game-sized maps. A recursive flood fill aborts the process ("Stack overflow", exit 134) on an open 256 x 256 map; .NET cannot catch a stack overflow. Use an explicit queue and mark a cell when it is queued, not when it is taken out, or it is queued up to four times.
- A
Listas a queue.RemoveAt(0)moves every element: TheAlgorithms' breadth-first fill took 1851 ms on 512 x 512,Regions.Label5 ms. UseQueue<T>. - A
Listas a visited set.Containsscans the list: TheAlgorithms' Dijkstra took 792 ms on a 128 x 128 grid,DistanceField.Build1.4 ms, with the same distances in every cell. Use abool[]or the distance array. - Search state stored on the nodes (cost, parent, open or closed): two agents searching at once, or on two threads, corrupt each other, and every search must reset what the last one touched. Keep the state in arrays the search owns.
- Equality that is not identity. TheAlgorithms' A*
Nodeis equal to any node with the same total cost. Equal must mean the same cell. - Unstable sorts.
List.SortandArray.Sortscramble equal keys: 40 items with keys 0 to 2 came out as ids 0, 36, 33, 30, 27. Sprites at the same Y swap draw order (flicker); units with the same initiative swap turns when one joins. Break ties with a stable key (spawn id) or use a stable sort (OrderBy, insertion sort). - Re-sorting what barely moved. 5000 sprites moving a little each frame:
Array.Sort0.46 ms a frame, insertion sort over last frame's order 0.10 ms, same result, and stable. Nodes haveYSortEnabled; this is for your own lists (MultiMesh instances, a turn queue). - Floating-point costs in a lockstep or replayed game can differ between machines;
DistanceFielduses integers.
4. The helpers
// One field for every enemy: rebuild when the player enters a new cell, not every frame.
var field = new DistanceField(width, height, diagonal: true);
field.SetCost(x, y, DistanceField.Blocked); // walls; 1 is floor, more is mud or a hazard to avoid
field.Build([playerCell]); // or every exit, every health pack: each cell gets the nearest
var next = field.Downhill(enemy.X, enemy.Y); // the same cell back means arrived, or walled off
field.Flee(); // the same field, for running away; a cornered agent stays put
var regions = Regions.Label(width, height, (x, y) => !wall[x, y]);
if (regions.Count != 1) { /* fill all but regions.Largest, or retry the next derived seed (procgen) */ }
var command = Suggest.Closest(typed, commands); // null when nothing is close enough to be the same word
- Distances are in tenths of a step: 10 for a plain step, 14 for a diagonal (
DistanceField.Straight,Diagonal). Diagonals never cut a wall's corner. DistanceFieldallocates nothing after its first build;Regions.Labelallocates its result.Suggest.Closestallows one edit up to six letters, two up to nine; a swap of two letters is one edit.
5. Data that must not loop
"acyclic": true on a field that refers to its own table makes the data runner (game-data) report every loop:
"techs": { "file": "data/techs.json", "id": "id",
"fields": { "requires": { "ref": "techs", "list": true, "optional": true, "acyclic": true } } }
It reports steam -> physics -> optics -> steam is a cycle: none of them can come first, and a missing id with its
near name: 'forge' requires names 'minning', which is not in techs; did you mean 'mining'?.
6. Exact solvers for small systems
When a system has a small state space (a puzzle, a crafting graph, a path), give it an exact solver. It powers autoplay, par scores, hints and generation:
- Tower of Hanoi: recursive optimal next move from any legal position. Toads and Frogs, Chinese rings, river crossing: breadth-first search. Lights Out: Gauss-Jordan elimination over GF(2), trying every free-variable combination for the shortest solution.
- Par = optimal + small slack. Generate starts by random moves from the solved state, or verify them with the solver.
- On a dead end, take back only as many moves as the solver needs to make it solvable again; a full reset is too harsh.
- Do not mark the start state with a sentinel move value (
-1) if-1can be a legal move; compare against the start state. - Show which pieces can act right now; it cuts frustration.
7. Prove it
- Test against a slow, obvious version on random small inputs (
RegionsAgreeWithUnionFindchecks labels against union-find on a random 40 x 30 grid). - Add one test at the largest size the game uses: an open 1000 x 1000 map catches recursion.
- Time it at that size inside the game (
bench,performance), not on a 10 x 10 example.
04 同仓库更多 Skills
over-budget
Use when a fixture exceeds the size budget.
bad-yaml
暂无简介
bad-workflow-description
Use when testing; runs the kit and then reads the JSON.
bad-version
Use when a fixture quotes a stale package version.
bad-value
Use when a fixture passes a value outside a parameter's set.
bad-trigger
Helps with Godot tests.