# UNDF: UNDF-2026-000000393
## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | MEDIUM |
| Component   | `net/minecraft/world/entity/ai/goal/MoveThroughVillageGoal.java` |
| Function    | `hasNotVisited(BlockPos)` |
| Hot path    | Called per AI tick for every village-dwelling mob |

## Defect

`MoveThroughVillageGoal.visited` is a `List<BlockPos>`. The method
`hasNotVisited(pos)` calls `this.visited.contains(pos)` — O(V) linear scan
per call, called inside the goal's tick loop: O(V²) per mob per tick.

```java
// BEFORE — O(V²): List.contains() inside per-tick loop
private final List<BlockPos> visited = Lists.newArrayList();

private boolean hasNotVisited(BlockPos pos) {
    return !this.visited.contains(pos);  // O(V) scan
}
```

Bounded at V≤15 by vanilla cap. Structural defect pattern; higher caps in mods
produce measurable overhead. Affects all villages mobs: villagers, iron golems, cats.

## Fix

Maintain a parallel `HashSet<BlockPos>` for O(1) membership testing.

```java
// AFTER — O(1): HashSet for contains(), List retained for clearing/iteration
private final List<BlockPos> visited    = Lists.newArrayList();
private final Set<BlockPos>  visitedSet = new HashSet<>();

private boolean hasNotVisited(BlockPos pos) {
    return !this.visitedSet.contains(pos);  // O(1)
}

// On clear: visited.clear(); visitedSet.clear();
// On add:   visited.add(pos); visitedSet.add(pos);
```
