Zombie pathfinding to unreachable targets causes server lag

I can confirm this bug. It's happened to me twice, both on the 23 and the 24 snapshots.
http://youtu.be/qftPV85ncYk

Client:

---- Minecraft Crash Report ----
// Why did you do that?

Time: 2013/06/13 9:58 PM
Description: Manually triggered debug crash

java.lang.Throwable
	at atl.k(SourceFile:1227)
	at atl.T(SourceFile:654)
	at atl.d(SourceFile:610)
	at net.minecraft.client.main.Main.main(SourceFile:85)


A detailed walkthrough of the error, its code path and all known details is as follows:
---------------------------------------------------------------------------------------

-- Affected level --
Details:
	Level name: MpServer
	All players: 1 total; [bcm['RandarTheBold'/1843, l='MpServer', x=-308.49, y=66.62, z=572.78]]
	Chunk stats: MultiplayerChunkCache: 420
	Level seed: 0
	Level generator: ID 00 - default, ver 1. Features enabled: false
	Level generator options: 
	Level spawn location: World: (-162,64,236), Chunk: (at 14,4,12 in -11,14; contains blocks -176,0,224 to -161,255,239), Region: (-1,0; contains chunks -32,0 to -1,31, blocks -512,0,0 to -1,255,511)
	Level time: 22384 game time, 22384 day time
	Level dimension: 0
	Level storage version: 0x00000 - Unknown?
	Level weather: Rain time: 0 (now: false), thunder time: 0 (now: false)
	Level game mode: Game mode: survival (ID 0). Hardcore: false. Cheats: false
	Forced entities: 100 total; [tr['Zombie'/1913, l='MpServer', x=-282.72, y=63.00, z=605.59], tm['Skeleton'/1912, l='MpServer', x=-287.66, y=15.00, z=609.06], tr['Zombie'/1915, l='MpServer', x=-280.97, y=62.00, z=610.31], tr['Zombie'/1914, l='MpServer', x=-284.03, y=63.00, z=604.88], tr['Zombie'/1917, l='MpServer', x=-276.94, y=61.81, z=621.42], rm['Cow'/1916, l='MpServer', x=-273.47, y=63.00, z=626.75], to['Spider'/1919, l='MpServer', x=-273.66, y=64.00, z=637.21], rm['Cow'/1918, l='MpServer', x=-282.72, y=65.00, z=628.31], tm['Skeleton'/1905, l='MpServer', x=-303.50, y=47.00, z=646.09], tm['Skeleton'/1904, l='MpServer', x=-291.50, y=53.00, z=621.88], rj['Bat'/1909, l='MpServer', x=-289.56, y=42.54, z=529.16], rj['Bat'/1911, l='MpServer', x=-283.63, y=54.60, z=596.41], tr['Zombie'/1910, l='MpServer', x=-285.50, y=16.00, z=606.50], to['Spider'/1896, l='MpServer', x=-305.75, y=64.00, z=536.50], tm['Skeleton'/1897, l='MpServer', x=-297.53, y=26.00, z=555.41], ta['Creeper'/1898, l='MpServer', x=-302.50, y=27.00, z=553.50], to['Spider'/1899, l='MpServer', x=-288.75, y=64.00, z=546.97], sn['item.tile.sandStone.default'/1900, l='MpServer', x=-301.91, y=64.13, z=571.09], rj['Bat'/1901, l='MpServer', x=-301.25, y=29.10, z=579.75], rj['Bat'/1902, l='MpServer', x=-297.25, y=26.10, z=582.75], rj['Bat'/1903, l='MpServer', x=-288.38, y=53.00, z=595.56], bcm['RandarTheBold'/1843, l='MpServer', x=-308.49, y=66.62, z=572.78], tm['Skeleton'/1893, l='MpServer', x=-290.69, y=42.00, z=536.44], to['Spider'/1894, l='MpServer', x=-288.66, y=64.00, z=542.25], sn['item.item.string'/1895, l='MpServer', x=-292.88, y=64.13, z=542.25], tm['Skeleton'/1883, l='MpServer', x=-332.06, y=69.00, z=629.03], tu['Villager'/1882, l='MpServer', x=-320.66, y=65.00, z=573.94], to['Spider'/1881, l='MpServer', x=-332.88, y=70.00, z=546.19], tm['Skeleton'/1880, l='MpServer', x=-323.53, y=66.00, z=548.94], to['Spider'/1887, l='MpServer', x=-307.47, y=66.00, z=631.53], rj['Bat'/1886, l='MpServer', x=-315.47, y=23.10, z=616.25], rj['Bat'/1885, l='MpServer', x=-303.53, y=20.57, z=522.38], tm['Skeleton'/1875, l='MpServer', x=-331.34, y=68.17, z=538.28], tm['Skeleton'/1874, l='MpServer', x=-324.50, y=65.00, z=493.50], tm['Skeleton'/1873, l='MpServer', x=-325.50, y=65.00, z=494.50], tm['Skeleton'/1872, l='MpServer', x=-346.50, y=65.00, z=583.50], to['Spider'/1879, l='MpServer', x=-333.73, y=70.00, z=544.25], tr['Zombie'/1878, l='MpServer', x=-321.69, y=66.00, z=548.02], tr['Zombie'/1877, l='MpServer', x=-322.59, y=67.00, z=548.06], to['Spider'/1876, l='MpServer', x=-331.34, y=68.00, z=538.28], ta['Creeper'/1866, l='MpServer', x=-361.50, y=70.00, z=607.50], ta['Creeper'/1867, l='MpServer', x=-357.94, y=70.00, z=610.31], rj['Bat'/1864, l='MpServer', x=-361.25, y=15.10, z=496.25], tr['Zombie'/1865, l='MpServer', x=-352.50, y=37.00, z=496.50], to['Spider'/1870, l='MpServer', x=-350.13, y=65.00, z=584.03], tm['Skeleton'/1871, l='MpServer', x=-350.19, y=65.00, z=582.63], tm['Skeleton'/1868, l='MpServer', x=-344.25, y=64.00, z=514.22], ta['Creeper'/1869, l='MpServer', x=-336.50, y=69.00, z=552.50], ta['Creeper'/1856, l='MpServer', x=-384.50, y=64.00, z=530.50], tm['Skeleton'/1857, l='MpServer', x=-384.50, y=69.00, z=615.50], tr['Zombie'/1841, l='MpServer', x=-338.94, y=68.00, z=600.63], tr['Zombie'/1840, l='MpServer', x=-333.44, y=65.00, z=593.38], ta['Creeper'/1842, l='MpServer', x=-304.59, y=64.00, z=603.06], tr['Zombie'/1836, l='MpServer', x=-312.91, y=64.00, z=577.69], tr['Zombie'/1837, l='MpServer', x=-314.56, y=64.00, z=576.34], tr['Zombie'/1838, l='MpServer', x=-332.53, y=65.00, z=594.31], tr['Zombie'/1839, l='MpServer', x=-331.97, y=65.00, z=593.41], nv['Experience Orb'/1832, l='MpServer', x=-310.24, y=65.17, z=577.25], tr['Zombie'/1833, l='MpServer', x=-305.06, y=64.00, z=578.94], tr['Zombie'/1834, l='MpServer', x=-303.03, y=64.00, z=577.28], tr['Zombie'/1835, l='MpServer', x=-315.74, y=64.00, z=573.84], sn['item.item.rottenFlesh'/1828, l='MpServer', x=-309.16, y=64.13, z=577.97], sn['item.item.doorWood'/1829, l='MpServer', x=-309.09, y=64.13, z=579.19], nv['Experience Orb'/1830, l='MpServer', x=-310.22, y=65.10, z=577.28], nv['Experience Orb'/1831, l='MpServer', x=-310.73, y=65.17, z=577.25], tr['Zombie'/1824, l='MpServer', x=-309.38, y=18.00, z=588.31], tu['Villager'/1825, l='MpServer', x=-311.75, y=64.00, z=585.38], tu['Villager'/1826, l='MpServer', x=-319.72, y=65.00, z=585.38], tr['Zombie'/1827, l='MpServer', x=-314.30, y=64.00, z=575.06], ta['Creeper'/1823, l='MpServer', x=-313.55, y=17.00, z=590.60], tr['Zombie'/1822, l='MpServer', x=-314.17, y=64.00, z=572.46], tr['Zombie'/1821, l='MpServer', x=-315.14, y=64.00, z=573.03], tr['Zombie'/1820, l='MpServer', x=-315.69, y=64.00, z=575.39], tr['Zombie'/1819, l='MpServer', x=-314.31, y=64.00, z=574.22], tr['Zombie'/1818, l='MpServer', x=-314.30, y=64.00, z=573.44], tu['Villager'/1817, l='MpServer', x=-312.47, y=65.00, z=573.63], tu['Villager'/1816, l='MpServer', x=-312.50, y=65.00, z=575.69], sn['item.tile.sandStone.smooth'/1815, l='MpServer', x=-308.22, y=62.13, z=573.44], sn['item.tile.sandStone.smooth'/1814, l='MpServer', x=-307.13, y=61.13, z=573.13], tu['Villager'/1813, l='MpServer', x=-318.14, y=64.00, z=592.86], tu['Villager'/1812, l='MpServer', x=-321.15, y=66.00, z=572.47], tu['Villager'/1811, l='MpServer', x=-321.44, y=65.00, z=577.66], tu['Villager'/1810, l='MpServer', x=-330.78, y=66.00, z=591.50], tm['Skeleton'/1942, l='MpServer', x=-244.13, y=66.00, z=495.59], ta['Creeper'/1943, l='MpServer', x=-250.50, y=37.00, z=537.50], rj['Bat'/1950, l='MpServer', x=-230.41, y=26.92, z=608.81], rj['Bat'/1951, l='MpServer', x=-240.16, y=40.00, z=606.25], tr['Zombie'/1949, l='MpServer', x=-234.50, y=65.00, z=499.50], tm['Skeleton'/1946, l='MpServer', x=-253.38, y=28.00, z=578.44], rj['Bat'/1947, l='MpServer', x=-240.25, y=40.10, z=606.53], ta['Creeper'/1944, l='MpServer', x=-246.50, y=37.00, z=538.50], rj['Bat'/1945, l='MpServer', x=-244.34, y=47.60, z=567.75], to['Spider'/1924, l='MpServer', x=-271.21, y=64.00, z=638.97], tm['Skeleton'/1923, l='MpServer', x=-273.50, y=64.00, z=645.50], tm['Skeleton'/1922, l='MpServer', x=-282.09, y=21.00, z=652.53], rj['Bat'/1921, l='MpServer', x=-272.25, y=24.10, z=648.34], rm['Cow'/1920, l='MpServer', x=-285.13, y=64.00, z=627.59], to['Spider'/1935, l='MpServer', x=-267.44, y=64.00, z=633.72], tr['Zombie'/1934, l='MpServer', x=-265.50, y=37.00, z=636.50], ta['Creeper'/1933, l='MpServer', x=-260.41, y=66.00, z=505.94]]
	Retry entities: 0 total; []
Stacktrace:
	at bcj.a(SourceFile:284)
	at atl.b(SourceFile:1789)
	at atl.d(SourceFile:619)
	at net.minecraft.client.main.Main.main(SourceFile:85)

-- System Details --
Details:
	Minecraft Version: 13w24a
	Operating System: Windows 7 (x86) version 6.1
	Java Version: 1.7.0_21, Oracle Corporation
	Java VM Version: Java HotSpot(TM) Client VM (mixed mode), Oracle Corporation
	Memory: 85770904 bytes (81 MB) / 314269696 bytes (299 MB) up to 1037959168 bytes (989 MB)
	JVM Flags: 1 total; -Xmx1G
	AABB Pool Size: 1523 (85288 bytes; 0 MB) allocated, 2 (112 bytes; 0 MB) used
	Suspicious classes: No suspicious classes found.
	IntCache: cache: 0, tcache: 0, allocated: 3, tallocated: 63
	Launched Version: 13w24a
	LWJGL: 2.9.0
	OpenGL: ATI Radeon HD 5800 Series GL version 4.2.12002 Compatibility Profile Context 9.12.0.0, ATI Technologies Inc.
	Is Modded: Probably not. Jar signature remains and client brand is untouched.
	Type: Client (map_client.txt)
	Texture Pack: Default
	Profiler Position: N/A (disabled)
	Vec3 Pool Size: 1650 (92400 bytes; 0 MB) allocated, 17 (952 bytes; 0 MB) used

Block destruction is where it is most noticeable. Also if you watch the moon, it moves, then glitches back a few seconds, then moves forward, then glitches back a few seconds. It is unplayable. You pretty much have to SLOWLY kill the zombies or just AFK until the sun comes up.

I'm getting this sort of lag too, with entities mainly for me, but I did notice some block placing/breaking lag. I looked in my console and I keep getting this:
"Can't keep up! Did the system time change, or is the server overloaded?"

This only seems to happen when there are a lot of Zombies around, which is hard to avoid seeing as their range is roughly 64-80 blocks away (from my tests anyway) for both Players and Villagers now.

I get that message on servers where the time on the server is off. A quick ntpdate sync and it goes away, or configure NTP. Not sure what you'd do on a windows server since I don't use it, but probably similar.

I got that in the Launcher console playing single player, so I'm not really sure what I can do in that regard. It isn't affecting me too badly, but for others with lower end systems, I can only imagine how bad it may be.

The dev version is a server, with 1 client: YOU! So probably the time on your workstation is off. Use a network time server and you never have to set it again.

The "Can't keep up" message throws also if dedicated server & client running on the same machine in high lag situations, so it is an indicator for lag.

You are right. I noticed I was getting these too last night during a lag/zombie siege event.

I'm getting really severe lag like this in snapshot 13w25c and not even having to deal with any sieges. I'm just mining! It's throwing the 'can't keep up' message very often whether I'm breaking a block or just walking around. Using Windows 7 64 bit, most recent version of Java.

More info on the recent lag in SP:

Tested lag using the old launcher, worked fine.
Tested lag using the new launcher and release 1.5.2, worked fine.
Tested lag using the new launcher and the snapshots from 13w25a, b, and c, all had the same lag problems.

May or may not be useful but eh. xD

This has been happening since snapshot 13w23b for me, when they changed how Zombies function. I too am not dealing with Villages/Villagers, just alone in a cave or on the surface.

I haven't tested the village again in a while, and I still don't get the block lag, but the timing message is now coming up more than normal. I can always feel when it is happening, then I look over to the console and see that it has happened.

Perhaps this is more related to a lighting recalculation or gravity? You might try the dump and submit it here when this happening.

From older bug report on block lag closed as duplicate of this (seems to make sense to put it all in one place):

I've been getting this at times too. Attaching a world save in case it helps with replication. I'm in a desert blacksmith, the chest in there my inventory has some dirt and sand blocks. I can place them without a problem, but on breaking them, they reappear for about a second before disappearing and dropping an item. I have rebooted my PC and used a different MC account, but with both the lag persists. Non-default settings in this world are largeBiomes generator, gamerule naturalRegeneration false, scoreboard objective deathcount, displayed in slot_0. The scoreboard and regen were set using NBTExplorer rather than commands, but I was able to play for quite a while after doing so without lag. The other lag I've noticed is the moon rising a bit then getting set back, resulting in time passing more slowly. I'm getting a framerate of about 50fps, and I can't see from Shift-F3 what's causing the lag.

Edit: using snapshot 13w24b

The forced crash report showed that there were quite a lot of zombies about. I opened up the world in MCEdit and deleted all nearby entities and the lag disappeared. I don't know how to be more selective and delete only zombies to check it was them and not any of the other entities, or anything unrelated that also gets modified by MCEdit (it relights modified chunks, I have no idea what other changes might've occured) but, erm... could it be related to 49 zombies converging on a village?

For me it seems related to the new zombie code (other zombies are attracted when one is attacked and villager reaction to a siege). I didn't have an incredible number of zombies, but everything else happens: time goes off, the moon snaps back. One time a villager just spun in a circle at incredible speed. I placed a block near him and he stopped and ran inside. Seems definitely related to the new zombie code, but probably more in relation to villages and block placement during a siege.

Sorry, last attempt was incomplete upload. I'm not sure if it's relevant, but I was playing on normal, so the zombies couldn't get to villagers because they couldn't break doors. Also, two of the doors were two blocks above ground level (generated that way) so zombies couldn't path in/villagers couldn't path out anyway.

This is happening to me too! I made a giant wall around the village I'm protecting and zombies are lining up on the outside causing the villagers to go crazy. I agree. It's probably related to the villagers reactions in relation to the sieges. All I know, is that if 1.6 is released with this bug people that are farming villagers or live in a village are going to be mad.

Still having this problem in the 1.6 pre-release. I don't believe this will be fixed before 1.6 is released so I guess the most I can do is offer a temporary 'solution.'

Since this problem is linked to too many zombies spawning during sieges, the best way to deal with it is to set the difficulty to 'Peaceful' until day. Not optimal but it'll have to do until this is addressed and fixed.

I don't have any lags with that.

I'm at Cisco Live this week. Not sure if I will get time to test this, but I will try ASAP with the pre-release and see if any other bug fixes fixed this. I saw nothing in the release notes that would have affected this bug, but you never know how a bug fix might cascade and 'fix' some other issue. More to follow when I can get a moment to check the right conditions. I have a map with 4 villages somewhat near each other so I can test this phenomenon fairly easily.

more to follow..

Just loaded up the attached world save in the pre-release, there's still just as much lag.

agreed. I just confirmed in my save. The lag is crazy. time can't keep up. the moon snaps back. zombies multiply, villagers go crazy. Still there in 1.6 prerelease.

I have this same issue, but mine does not involve a village. When I hit a zombie and all his friends come to join the party my game freezes. I have to (alt)+(tab) to get swap to the load screen and then back to the pause screen. I then can save and quit, to reload which fixes the problem (until the zombies agros again)
It's so bad, I've paused playing the game until it can be fixed (or I buy a souped up turbo PC to play on)

This is happening to me (dedicated server, version 1.6.1) with a village I've been renovating. Every single night the village is mobbed by 10–15 zombies and immediately the server starts lagging to the point that the game is unplayable. The day/night cycle stops, crops don't grow, furnaces stop smelting; mobs barely move, take an entire second to register they've been hit, moonwalk or slide backwards.

iStat is showing no higher CPU usage than usual from Java, but the server is crying for mercy. It takes about 20 seconds to even shut the server down from issuing the stop command. Other applications are unaffected. I don't understand what's going on.

How can I force a server crash? Or do I have to load the world in singleplayer to get a crash report?

Is this still a concern in the current Minecraft version? If so, please update the affected versions in order to best aid Mojang ensuring bugs are still valid in the latest releases/pre-releases.

Yes, it applies to 1.6.1. How do I update the affected versions? JIRA is really difficult to use.

Unfortunately only the creator can, or a moderator.

Thanks. What is the requirement to have this marked as confirmed? Seems like multiple people are having the same problem. Can I attach an affected world?

I've attached the world where I'm having this problem, pruned down to just the village. It's currently in the midst of a zombie siege and the spawn is set to the middle of the village for ease of demonstration.

I've also discovered more information about the bug. There are two buildings with the doors blocked off by dirt here because villagers are stupid and think sunrise = safe. If you find the two barricaded houses and break the dirt blocking their doors, the game will suddenly fast forward for a couple of seconds and everything will run as normal. Seems the bug is triggered when the zombies can't find a path to the villagers.

I haven't tried loading it in single-player, so be sure to try the dedicated server jar if single-player doesn't manifest the bug.

I'd like a minor clarification; do the zombie/lag problems possibly start before midnight (e.g. observe the moon position on the sky to know midnight), or at exactly or very soon after midnight? (As a background for this question, the real zombie sieges were supposed to start at midnight (if at all during that night), and spawned rapidly (in few seconds) up to 20 extra zombies in or near one location in the village.)

Just trying to figure out whether this is related to the actual zombie siege event, which has been broken (i.e. never happens) for quite a while, or if that bug (MC-7432) has been finally fixed without being marked so by Mojang (and giving, as usual, another bug in its place), or if this is "only" related to normal zombie spawning. Note, normally spawned zombies and siege spawned zombies are just the same ones and behave the same way in or near village doors and/or villagers.

EDIT: I can not check/confirm the status of MC-7432 myself until MCP catches up... With as large changes to zombies as this bug indicates, checking the source code is the only way to be certain.

I notice someone already updated the 1.6.1. sorry, been at cisco live 2013 in orlando this week - at the same location as Minecon will be this year ironically. 🙂

In my testing zombie hordes occasionally got as large as 10 or more and was well past the midnight timeframe.

Although the lag would occur even at times that only a few zombies (<5) showed up.

I've had this issue and I believe that it is caused when zombies cannot find a clear path to user/villager. I cannot upload a save file to prove this as I have a data cap but when in open space a large number of zombies (8) caused no lag to me. When I stood on a 4x4 area (just me no mobs) surrounded in lava, the lag exploded. Mobs barely moved, the moon jumps back and forth. I am playing in the 1.6.1 release and have had the issue since around 13w23b or around there. It is incredibly tedious to me that it has been an issue for so long and there has been non public recognition of it from Mojang despite it being a huge issue. I can however attach a screenshot to show what I mean.

This doesn't really prove much but it is to show that when stood here and the zombies cannot reach me safely it causes incredible lag of all sorts. When I jump off it, the game 'catches up' and goes turbo for a few seconds as it tries to get to real time.

We are having the same problem on our server, though it has nothing to do with the sieges. Every night our server peaks real bad which cause block lag. Whenever we kill off the zombies or they die at daybreak the server cools down and the block lag disappear.

Edit: We're on 1.6.1

Not sure how the peaceful mode plays into this since no mobs were generated when I play on peaceful. The bug appears when zombies are generating and attacking villagers, so those conditions must be met. No lag occurs when I am on peaceful in the middle of village at any time during the night. I tried twice, two nights with two different villages on peaceful. No lag was experienced.

Just vote it up. I haven't had this issue, therefor I won't vote it. If you have had this issue, vote for it.

I can't vote since I reported it, so please all commenters/watchers, vote!

Hopefully this is resolved soon as it is really preventing me from enjoying the game. Quite a number of votes also.

I uploaded a video that may help show off this bug in action. Note that it isn't going to show Villagers/Villages, as it happens regardless it seems, if you are in one or not. Thanks to some people that commented about the whole "unreachable path-finding lag", I tried it out myself and the issue seems to be the problem people are having. You can try it out for yourself if you'd like, using whatever methods you want, I just wanna help out and get this bug fixed, it is very annoying. Not the best video but it will do enough I hope, I'm not a professional or anything.

http://youtu.be/GflhCHfSETk

On my issue report for it (which was on a server and didn't involve a village at all) https://mojang.atlassian.net/browse/MC-20740 it has a screenshot of the profiling done, a long with a link to how to view the profiling report.

According to profiling of minecraft_server.jar using mcp for mappings, it has the "net.minecraft.src.EntityAIAttackOnCollide.updateTask()" as taking the most time.

in that particular task it basically does the zombie path finding, which they can now do from 80 blocks away.

@Loren: You might want to adjust the issue title, as it seems (according to other comments) that it is not related to the actual zombie sieges, but to zombie's path finding in general (or at least when related to attacking or something).

@Jack: 3 weeks and 20 votes? Pfft. Check the most popular issues -list; more than half a year old issues and 395 votes and still there.. or MC-3, just as old with 77 votes and source code for fix is provided, still there... However, I have noticed that recently introduced bugs tend to get fixed soon(er) than the old ones, and this one is quite severe too, so I think there is hope.

After some troubleshooting i tried yesterday im fairly sure there is an issue with the zombies. I cant really confirm one way or the other if it has to do with zombies trying to get to villagers, or zombies trying to get to a player, or just zombies being zombies. I can agree that something is certainly wrong here and it is effecting the quality of play for a lot of people. Whatever the issue is causes the server, or the client in single-player scenarios, to become overworked or overloaded whenever the issue arises. Blocks reappear when broken, it takes a number of seconds to pick up a broken block, monsters behave strangely, attacking monsters is extremely sluggish, taking damage is extremely sluggish, and pretty much any other "lag" type of effect occurs during the issues discussed here. Please make this a priority, thanks mojang!

I noticed this on the server I run for some of my friends. It made the game unplayable at night time because our base is centered on an npc village. I tested it in single player and got the same results. I'm not trying to advertise, but I made a video that covers more of the issues if anyone's curious. http://youtu.be/hEcINIdVEtI

I am having this same problem. I am on a mid-to-low end computer and it makes the game unplayable. If I change to peaceful, lag disappears. Please vote on this so it will shoot up the charts and maybe get fixed by 1.6.2 because, as is, MC is almost unplayable on anything other than peaceful. 😞

It makes sense that having a large number of entities that track targets over four times as far away than they used too would cause problems. With villages they also have multiple targets to consider. Guess I'm just going to forget my plans of living in a village.

@Preston: both assumptions might be valid, but, iirc, zombies at least used to target only one thing at a time, so the villager count should not affect. Of course, Mojang could have changed it.

The rapid large lag sounds more like classical O(N^2) (or worse) mistake in some overall algorithm.

Since MCP for 1.6.1 has arrived, I might take a look during weekend.

@Markku If you want to see where, i have taken a screenshot of the profiling on my server where i have drilled right down from the onUpdate task for EntityZombie to the hash itself:

http://puu.sh/3vrB4.png

This is a major issue for SMP. Villages are ghost towns because the lag is unbearable. Tick spikes to 300+ and everything goes slow-mo. Leaving a village chunk area instantly removes the lag.

Everyone vote! My server can't even start up because 1000's of zombies

As a work around you can bring it up in peaceful, kill the zombies, then restart in normal. 🙂 ? maybe??

crazyman, use mcedit to delete all entities?

Read this comment instead:
https://mojang.atlassian.net/browse/MC-17630?focusedCommentId=92590&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-92590

— Old stuff below —
I was able to dig it down enough to confirm that the reason is at least partially the large maximum pathing range for zombies. "Partially", because while the zombies are the only ones doing the large distance pathing, and that path searching is the cause of the symptoms, the large range in itself is not "incorrect".

Testing
When I limited maximum pathing range value (or at least the value that affects the range) to only 16, everything worked smooth, CPU load around 10%-15% (pretty much the same as at day time/no zombies, with or without the change). If I allowed it to be as normal, I got various range values upto about 100, and even my somewhat beefy system started showing the described issues (only for Minecraft, though), with CPU load around 25%-30%. (For reference, I made the limit at PathNavigate.getPathSearchRange(), so it affected all kinds of pathing. I noticed there are more call paths with large ranges than what is shown in the profiler reports.)

Wiping existing monster and adjusting zombies' "extra" range attribute to a humble 2, and getting a new bunch of zombies, that also seemed to help with things, but then the zombies didn't come rushing to the village. (Well, perhaps for the best, as the small village is butchered in the first night even without the "real" zombie sieges and in normal difficulty. Even if the doors won't break, zombies are able to hit enough through doors to eventually kill the villagers, especially when one of the villagers inside get infected.)

Nerd-talk
The real issue seems to have been there all the time, but the new larger zombie pathing max range reveals the problems.

The pathing system (PathFinder and below) is somewhat, say, badly optimized. They work basically O(range^2) (every nerd goes "gotcha" at that), if not worse, as the algorithm apparently wants to store every location in the range for each new path search, and stores those points in a quite naive solution of a map. Or more correctly, two maps, the other being inside java.util.HashSet, used by the first map implementation. Both start with initial size of 16, and the large distances typically store more than 40,000 points to the maps (for each path search!), so there is another (edit: big-oh issue) efficiency issue there from the multiple re-growths... At least, the helper data structures should be pre-allocated with the estimated needed full size (edit: per search, unless reusing PathFinder instances). The IntHashMap should perhaps use a bit more advanced implementation (though I did not even try to analyze usage patterns, the current implementation could be just fine).

Without analyzing the actual path search algorithm, I just wonder why it has to store so many points, even when the zombies are already in 5-6 block's distance from their target. Sure, there could be a "backdoor" tens of blocks away, but while looking for that backdoor, typically only a minor share of points need to be considered before the typical case of either "no path at all" or "already found shortest possible" can be resolved.

Also, even without touching the current pathfinder, a crude optimization might be to reduce the calls to the full pathfinding. When the target is near, use a simpler and more limited path finder (or simply restrict the range of the current implementation to few more than the direct distance to target), and only call the full path finder and full range when the target is further away or the simpler version doesn't give results. And when the algorithm(s) decide that there are no paths, perhaps no need to call it again every second or so.. Currently it seems to be called with the full "power" unnecessarily often.

As I don't know if the path finder does or doesn't do it, this may be unnecessary speculation: it might be possible to optimize the routine to work around both entity and its target greedily, thus quickly finding out if there are no paths at all. Villagers are often closed in relatively small houses, and the zombies could be blocked in traps. (The current routine might already do something like that. But certainly doesn't feel like it.)

There are plenty more of optimization possible, even radical ones, but I think it would be best to do the easier ones first, as they should already be enough to solve this issue.

@Markku nice testing. Yeah, the profiling basically gives up after a while, i guess it notices that there is recursiveness happening, notices it occurs quite a few times, then simply gives up going any deeper. It is interesting to see that the issue has always been there too.

I didn't notice recursion (though there could be at some low level, I didn't check so carefully). The profilers may look like showing recursion, due to the obfuscated code having several methods with the same name (but different parameters).

Have you tried this testing with the 1.6.2 pre-release snapshot that they will be releasing on Monday? according to Dinnerbone there are 3 hidden fixes, would be interesting to see if they have fixed it without saying they fixed it (highly doubtful though).

I spend plenty enough time and effort to find/fix bugs Mojang doesn't, to not waste more looking for things "hidden" on purpose. Considering the extra time it takes to prepare each new version (even if MCP would always be ready for new versions), when it comes to doing things at source code level, I only work on a small subset of versions, typically the official releases. Also, that kind of "test if it has been fixed" should be reserved for cases where Mojang can not ensure the issue is fully fixed (and tells about such situation here). Otherwise the issue is either resolved (fixed/wont fix/intended/etc) or kept open, simple as that.

However, I think I will notice/can check whether this is fixed (or at least improved enough) even without looking into the code or using other tools, as the symptoms were quite clear even in the game. The easiest, no-interpretation needed -way for me was to kill a few zombies from a bunch of 20ish and see if the xp-orbs would get collected properly, though there are other quite obvious symptoms.

That's what i meant, no in-depth checking, since that would be insanely difficult without MCP mappings. I mean, i could update my server and have the whitelisted people on it update their clients, and it would take us all of about 2secs to test it, hell, i could tell if it is fixed just by looking at the server screen on my client, if it drops from 1.5secs to 0.3secs then it is most likely fixed.

From MC-20765:
Maybe this can help:

Something's taking too long! 'root.levels.paradise.tick.entities.regular.tick.ai.newAi.goalSelector.goalTick.pathfind' took aprox 261.523724 ms
Something's taking too long! 'root.levels.paradise.tick.entities.regular.tick.ai.newAi.goalSelector.goalTick' took aprox 262.027559 ms
Something's taking too long! 'root.levels.paradise.tick.entities.regular.tick.ai.newAi.goalSelector' took aprox 262.307236 ms
Something's taking too long! 'root.levels.paradise.tick.entities.regular.tick.ai.newAi' took aprox 262.701753 ms
Something's taking too long! 'root.levels.paradise.tick.entities.regular.tick.ai' took aprox 262.92655 ms
Something's taking too long! 'root.levels.paradise.tick.entities.regular.tick' took aprox 263.271346 ms
Something's taking too long! 'root.levels.paradise.tick.entities.regular' took aprox 467.872884 ms
Something's taking too long! 'root.levels.paradise.tick.entities' took aprox 468.349919 ms
Something's taking too long! 'root.levels.paradise.tick' took aprox 473.432748 ms
Something's taking too long! 'root.levels.paradise' took aprox 473.944583 ms
Something's taking too long! 'root.levels' took aprox 474.510017 ms
Something's taking too long! 'root' took aprox 476.359478 ms

Only during nighttime.

@Kumasasa: Not as much as the JVM-profiler results, as those 'root.levels..' informations are not as easy to track into the code. Anyway, that '...goalTick.pathfind' happens to correspond to method World.getPathEntityToEntity(), which uses the PathFinder that I considered to be the "bad" (or at least worst) part of the problem reasons. So at least everything seems to point to the same direction and gives more trust that I found the right spots.

The culprits are now known, the task that remains is to decide which of them to change and how.

Tested the new snapshot.
Nothing has changed.
If they can't reach you: 100% cpu usage and lag

Still not fixed in 1.6.2 release.

My normal framerate is 30-40 fps, sometimes over 50 - even when loading chunks. The zombies drove it down to 5, often as low as 3.

I don't fully understand the zombie siege mechanic, but the wiki says it happens only with larger villagers (I've two villagers in two houses), so I guess this was just a few zombies that by the end turned into over a dozen. The first three walked back and forth around my house, ignoring a new door I added to try to get them in where I could fight them without endangering the villager.

The night before, I had the same sort of thing happen. I quickly associated the lag with zombies trying to path to a place they couldn't reach, and, not one of my most genius moments, unblocked the door thinking to block it in a new way or try to kill the zombies. While it was still too laggy for me to do anything productive, the zombies waltzed right past me to kill one of the villagers then ate my brains. I was annoyed; it took forever to find a village to begin with and I started with only three villagers, plus when I flew back the zombies were gone so I couldn't even heal the one who died.

While I hope you'll clear up the lag soon, I also hope you'll consider letting players turn off the zombie siege mechanic via the options menu. Since before Beta I've been learning how to make properly lit and protected areas, and now I've got villagers to protect, so the idea of having baddies spawn inside my well-defended perimeter just rubs me the wrong way... and being able to fight them (if I'm not down mining) or avoid the night (if I use a bed every single night) is insufficient.

I think we shouldn't include the zombie siege mechanic in it, that mechanic has been in place since beta 1.8 at least, and back then it didn't cause any issues at all, i think the biggest problem just comes right down to the new distance they can detect from and to an extent the 'call my buddies' feature.

Personally i like and have always liked the zombie siege mechanic, makes you come up with new ways to protect your villagers, i've often thought of a piston mechanism that blocks off all the doors at a certain time of the night, though you can't fully be guaranteed the stupid villagers have gone into any of the houses.

Yes, some players really like that ("force me to play differently, yay") and some don't ("seems out-of-keeping with MC mob behavior, boo"), which is why I suggest it be changed to an optional mechanic. (I'm active in the modding community and could get a mod easily enough to just turn it off, but I don't think a mod ought to be necessary - this should be a option in vanilla Minecraft.)

But yeah, like I said, though I at first assumed it was a zombie siege, I looked it up on the wiki and it doesn't seem to be. I think you're right about it being a combination of new factors, as it certainly wasn't doing this before the horse update.

Once this issue is fixed, or hopefully will be, such an option as to 'turn off' the zombie pathfinding mechanic won't be needed.

My server is too having the same issue:

Quad Xeon 4.2Ghz quad core system with 18GB ram.

Top indicates Java isn't using that much more CPU than normal and we have MySQL and Minecraft installed on SSD and minecraft runs from a 10GB ramdisk. This kind of lag shouldn't happen, this server borders on supercomputing.

I can also confirm that it is a null pathing issue. When a zombie agros a player or villager and cannot find a route, whether it be one zombie or 100, the server lags.

I'm going to assume and go out on a limb, not being a java expert but a PHP, C++ expert that the issue lies in too much CPU time being taken to find a new route.

A simple fix for this would be for a zombie to try to find a route once or twice, if that fails, it either attempts to find another target, despawns, or idles as an ambient monster.

Please fix this asap, as many server owners like myself are very much considering rolling back to 1.5.

Alethia and Ray:
The actual village/zombie siege is not the reason for this - that feature is not currently even working at all (haven't been for quite a while). Though if it did work, things would be just as much worse.

This is simply badly designed/coded path finding combined with just as badly designed AI calling that path finding too often (for example, because it doesn't even try to remember the previous result and check if that would still be usable).

Michael:
No need to guess, I already did the checking/testing part to confirm it is the combination of calling path finding too often and the path finding algorithm being quite unoptimized. Also, what you describe as a "simple fix" is not a fix, but a workaround, causing its own problems (though certainly minor compared to what the current situation causes). I have already explained some real fixes (and also workarounds) in an earlier comment: https://mojang.atlassian.net/browse/MC-17630?focusedCommentId=84646&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-84646

Please vote this up. 1.6.2 has still not fixed this issue.

No point in adding a comment about voting up; it is only noticed for some minutes on the activity stream (if anyone bothers to scroll on the few pages it is visible to see that in the first place), and so far, having high votes does not seem to have much correlation with the order Mojang fixes things. The best avenue to lure more votes (if one really thinks the vote count matters) is forums; a thread in suitable section can be bumped up occasionally, and will have much more visibility after each activity.

All that a vote-asking comment achieves is to bury possibly useful comments in the collapsed comment section, which Mojang apparently does not read much (if at all, judging from an issue where suitable fix was waiting, and Mojang didn't use (and as it happens, subsequently failed in fixing the bug)).

People vote things up when they find a bug annoying enough to get their full attention, exactly as it should be. This bug is already among those with vote counts increasing the fastest. Amazingly fast, really, just compare against some of the top voted entries which are among the oldest issues (practically as old as this Mojira), and are still only at 20-150 votes level. Sure some few have gathered few hundred votes, but apparently for now effect. Out of top 12 issues, at least 3 have fixes or at least tested significant improvements in their comments (and two of those have had them for months, and also a fourth issue but with a bit laborous fix), yet nothing happens...

Got this out of the log file. Never had this issue before 1.6
And before you even say it, its not my PC.

So I've found a way to sorta control the CPU a bit better, it's using the /gamerule command to just make it always day. The CPU is still higher than normal, but it's more manageable and I get fewer complaints from the players on my server. We don't have nightfall for now, but it's a trade off we've agreed is better than the CPU being 100%.

/gamerule doDaylightCycle false
/time set 6000 (I think that's the one for mid day).

At least on my server night time is when the CPU uses up all the cores on my server and I'm completely at 100% CPU usage. Doing the always day thing I'm still in the 80% to 100% mark for 1 core, but rarely goes into other cores.

I run a small to medium sized dedicated bukkit server and for over a week I've been tearing my hair out trying to figure out why my server lags in 1.6 where in 1.5 it did not. I juggled my plugins around, enabling, disabling, updating them. I ended up deciding to just run vanilla for a while thinking it was bukkit, but I got the same lag on vanilla. It only happens at night and I have suspected it was the zombie AI. So this past week I've been keeping the sun frozen in the sky because if I don't night will last 15-20 min with the stars jumping around. Also I have tried to switch hosts and that didn't help at all.

Came across this post just now. Decided to really test zombie AI to see if it was the issue. With nobody on my server, and me in creative, I spawned in 50 zombies, switched to survival, ran around a little bit then messed with their path tracking by blocking myself in. With only myself online, the stars were jumping around and I had quite a bit of entity lag.

I'm glad I found this bug report and I hope this helps! ~Troy

As some new commenters do not bother to read older comments, a link back to the buried earlier comment with my analysis (in short, the reason is already known):
https://mojang.atlassian.net/browse/MC-17630?focusedCommentId=84646&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-84646

Improvement (a.k.a. partial fix)

MCP naming (and a bit of my own)...

EntityAIAttackOnCollide

...
    private int rePathingDelay; // field_75445_i
    
    // part of FIX:
    private double pathedTargetX; // Leaving these uninitialized, evul me.
    private double pathedTargetY;
    private double pathedTargetZ;
    private boolean previousPathingOk = false; // Not really needed here, but an idea for future...
    ...
    public void updateTask() {
        EntityLivingBase var1 = this.attacker.getAttackTarget();
        this.attacker.getLookHelper().setLookPositionWithEntity(var1, 30.0F, 30.0F);

// OLD:
//        if ((this.forcePathing || this.attacker.getEntitySenses().canSee(var1)) && --this.rePathingDelay <= 0) {
//            this.rePathingDelay = 4 + this.attacker.getRNG().nextInt(7);
//            this.attacker.getNavigator().tryMoveToEntityLiving(var1, this.speed);
//        }
// NEW:
        double targetDistanceSq = this.attacker.getDistanceSq(var1.posX, var1.boundingBox.minY, var1.posZ);
        if (this.rePathingDelay > 0)
            --this.rePathingDelay;
        
        if (this.forcePathing || this.attacker.getEntitySenses().canSee(var1)) {
            boolean repath = false;
            double targetMovement = var1.getDistanceSq(pathedTargetX, pathedTargetY, pathedTargetZ);
            
            // Only do a new path search if enough time has passed from the previous search, and the target has moved:
            if (rePathingDelay <= 0) {
                if (targetMovement >= 1.0D) {
                    repath = true;
                }
            }
            // Ensure an occasional pathing if it would not be happening otherwise (e.g. to work when world
            // changed, or to work around any other unnoticed needs, or effects of future changes in code):
            if (!repath && rePathingDelay <= 0 && this.attacker.getRNG().nextInt(200) == 0) {
                repath = true;
            }
            
            if (repath) {
                previousPathingOk = this.attacker.getNavigator().tryMoveToEntityLiving(var1, this.speed);
                pathedTargetX = var1.posX;
                pathedTargetY = var1.boundingBox.minY;
                pathedTargetZ = var1.posZ;
                this.rePathingDelay = 4 + this.attacker.getRNG().nextInt(7);
                // A longer delay for longer distances, or if the pathing failed
                if (targetDistanceSq > 256.0D) { // > 16 blocks
                    if (targetDistanceSq > 1024.0D) { // > 32 blocks
                        this.rePathingDelay += 8;
                    } else {
                        this.rePathingDelay += 16;
                    }
                } else if (!previousPathingOk) {
                    this.rePathingDelay += 24;
                }
            }
        }
        
        this.attackTick = Math.max(this.attackTick - 1, 0);
        double var2 = (double) (this.attacker.width * 2.0F * this.attacker.width * 2.0F + var1.width);

//        if (this.attacker.getDistanceSq(var1.posX, var1.boundingBox.minY, var1.posZ) <= var2) {
        if (targetDistanceSq <= var2) {
        ...

With the above changes, the CPU load gets some peaking when loading a world (as both villagers and zombies will all do AI decisions and pathing again), but it stabilizes in 10-15 seconds to idle levels (for me 10%-12%). The CPU load can still occasionally peak at high values (for me 15%-20%) for 1-2 seconds. The overall average level is much nicer, and observable "lag" was almost totally gone.

The peaks come when the target(s) move and all zombies (that targeted the moving entity) will repath for a moment. In case of a continuously moving target (like fleeing villager/player), the load and lagginess can still be there (though seemed to be helped a bit). However, in a typical case, such situation can not continue for long (villager dies or all involved entities move out of range, player kills zombies, etc.). And also, typically, in such case there is a path from zombie(s) to target, and the lag has been problem with there is no path.

The biggest problem seemed to be with the villagers just standing inside their homes while zombies bash the doors, and the above change handles that situation just fine.

Feedback is welcome, especially if anyone is able to test those modifications with a less beefy (or more heavily loaded) system.

EDIT2: My bad for the part below.

The other change I had made was in the world; the zombies were not without path..

The optimization part below is still a valid one, but doesn't solve anything. The distance squared is apparently just as correct as distance for the algorithm used.

EDIT: Even bigger improvement (a.k.a. a real bug and real fix)

Although this alone makes a huge difference (even bigger/better than the above one) and works also when a bunch of zombies are chasing villager(s), I recommend having both sets of changes.

The real bug is that the method is adding squared distances, and then also comparing those borked values with other squared distances. Can't do that! (It is okay to compare two squared distances to each other, though, as the square-function is monotonic). Changing the calculations to use normal distance (i.e. calculating square roots) made the path finding method work much more efficiently. They still do occasionally produce large point sets (when the zombies are still far away) as expected, but with the fix, when they are near the target, the point set sizes stay less than couple hundred (instead of the non-fixed 40000+).