{"id":357275,"date":"2024-05-20T23:47:20","date_gmt":"2024-05-20T23:47:20","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=357275"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-20T23:47:20","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=357275","title":{"rendered":"<span>\u0421\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u043f\u0443\u0442\u0438 \u043d\u0430 Go \u0431\u0435\u0437 \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u0438 \u0421\u041c\u0421<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432\u0430\u0436\u043d\u044b. \u041d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0438\u0445 \u043c\u043e\u0436\u043d\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043e-\u0440\u0430\u0437\u043d\u043e\u043c\u0443.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0438 \u043e\u0434\u043d\u043e\u043c \u0438 \u0442\u043e\u043c \u0436\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u0432 \u0442\u044b\u0441\u044f\u0447\u0443 \u0440\u0430\u0437 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043d\u0430\u0438\u0432\u043d\u043e\u0439.<\/p>\n<p>  <\/p>\n<p>\u041b\u044e\u0431\u0438\u0442\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0442\u0440\u044e\u043a\u0438 \u0441 \u0431\u0438\u0442\u0430\u043c\u0438? \u0422\u043e\u0433\u0434\u0430 \u0441\u043a\u043e\u0440\u0435\u0435 \u043f\u043e\u0434 \u043a\u0430\u0442!<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/nn\/wj\/8m\/nnwj8mo5yr20jfueyowen6u-pbw.png\" data-src=\"https:\/\/habrastorage.org\/webt\/nn\/wj\/8m\/nnwj8mo5yr20jfueyowen6u-pbw.png\"\/><\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<h2 id=\"intro\">\u0418\u043d\u0442\u0440\u043e<\/h2>\n<p>  <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f: A-star \u0438 <abbr title=\"Greedy best-first search, \u043d\u0435 \u043f\u0443\u0442\u0430\u0442\u044c \u0441 breadth-first search\">greedy BFS<\/abbr>. \u041e\u0431\u0430 \u043e\u0442\u043b\u0438\u0447\u043d\u043e \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043d\u044b \u0432 \u0441\u0442\u0430\u0442\u044c\u0435 <a href=\"https:\/\/www.redblobgames.com\/pathfinding\/a-star\/introduction.html\" rel=\"nofollow noopener noreferrer\">Introduction to the A* Algorithm<\/a>.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0438\u0441\u043a \u043f\u0443\u0442\u0438 \u043c\u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u043b\u0441\u044f \u0432 \u0438\u0433\u0440\u0435 <a href=\"https:\/\/github.com\/quasilyte\/roboden-game\" rel=\"nofollow noopener noreferrer\">Roboden<\/a>. \u041d\u0430\u043f\u0438\u0441\u0430\u043d\u0430 \u043e\u043d\u0430 \u043d\u0430 Go \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0434\u0432\u0438\u0436\u043a\u0430 <a href=\"https:\/\/github.com\/hajimehoshi\/ebiten\/\" rel=\"nofollow noopener noreferrer\">Ebitengine<\/a>, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u044f \u0438\u0441\u043a\u0430\u043b \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u044f\u0437\u044b\u043a\u0430.<\/p>\n<p>  <\/p>\n<p>\u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u2014 \u043e\u043d\u0430 \u043d\u0435 \u043f\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0430 \u043f\u0440\u043e \u043c\u0438\u043a\u0440\u043e\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043f\u0440\u043e\u0447\u0438\u0435 \u0445\u0438\u0442\u0440\u043e\u0441\u0442\u0438. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0438, \u0447\u0442\u043e\u0431\u044b \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u043b\u0443\u0447\u0448\u0438\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e \u043f\u043e\u0434 \u043d\u0435\u0451.<\/p>\n<p>  <\/p>\n<p>\u0418 \u0445\u043e\u0442\u044f \u044f \u0431\u0443\u0434\u0443 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0438\u043c\u0435\u043d\u043d\u043e \u043d\u0430 Go, \u043c\u043d\u043e\u0433\u0438\u0435 \u0438\u0437 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u0439 \u0438 \u0442\u0440\u044e\u043a\u043e\u0432 \u0431\u0443\u0434\u0443\u0442 \u0443\u043c\u0435\u0441\u0442\u043d\u044b \u043f\u043e\u0447\u0442\u0438 \u0432 \u043b\u044e\u0431\u043e\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043d\u0438\u0437\u043a\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<\/p>\n<p>  <\/p>\n<h2 id=\"suschestvuyuschie-biblioteki\">\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438<\/h2>\n<p>  <\/p>\n<p>\u041e\u0442\u043a\u0440\u044b\u0432\u0430\u0435\u043c <a href=\"https:\/\/github.com\/sedyh\/awesome-ebitengine\" rel=\"nofollow noopener noreferrer\">awesome-ebitengine<\/a> \u0438 \u0438\u0449\u0435\u043c \u043c\u043e\u0434\u0443\u043b\u0438 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438:<\/p>\n<p>  <\/p>\n<ul>\n<li><a href=\"https:\/\/github.com\/fzipp\/astar\" rel=\"nofollow noopener noreferrer\">github.com\/fzipp\/astar<\/a><\/li>\n<li><a href=\"https:\/\/github.com\/beefsack\/go-astar\" rel=\"nofollow noopener noreferrer\">github.com\/beefsack\/go-astar<\/a><\/li>\n<li><a href=\"https:\/\/github.com\/kelindar\/tile\" rel=\"nofollow noopener noreferrer\">github.com\/kelindar\/tile<\/a><\/li>\n<li><a href=\"https:\/\/github.com\/s0rg\/grid\" rel=\"nofollow noopener noreferrer\">github.com\/s0rg\/grid<\/a><\/li>\n<li><a href=\"https:\/\/github.com\/solarlune\/paths\" rel=\"nofollow noopener noreferrer\">github.com\/solarlune\/paths<\/a><\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u041c\u043d\u0435 \u0432 \u043c\u043e\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u043d\u0443\u0436\u0435\u043d \u043f\u043e\u0438\u0441\u043a \u043f\u043e <abbr title=\"Grid\">\u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435<\/abbr>, \u0431\u0435\u0437 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0440\u0430\u0441\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445 <abbr title=\"Key waypoint\">\u0442\u043e\u0447\u0435\u043a \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430<\/abbr>. \u041a\u0430\u0436\u0434\u0430\u044f \u0438\u0437 \u044d\u0442\u0438\u0445 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0434 \u044d\u0442\u0438 \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u041d\u0430\u043f\u0438\u0448\u0435\u043c <a href=\"https:\/\/github.com\/quasilyte\/pathing\/tree\/master\/_bench\" rel=\"nofollow noopener noreferrer\">\u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438<\/a> \u0438 \u0438\u0437\u043c\u0435\u0440\u0438\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u044d\u0442\u0438\u0445 \u043f\u0430\u043a\u0435\u0442\u043e\u0432. \u0411\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u0441\u0432\u043e\u0438\u043c\u0438 \u043a\u0430\u0440\u0442\u0430\u043c\u0438 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438: \u043e\u0442 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432 \u0434\u043e \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u043e\u0432. \u041a\u0430\u0436\u0434\u044b\u0439 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u043d\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c 50&#215;50 \u043a\u043b\u0435\u0442\u043e\u043a.<\/p>\n<p>  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u0411\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430<\/th>\n<th>\u0422\u0435\u0441\u0442 no_walls<\/th>\n<th>\u0422\u0435\u0441\u0442 simple_wall<\/th>\n<th>\u0422\u0435\u0441\u0442 multi_wall<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>astar<\/td>\n<td>948367 ns<\/td>\n<td>1554290 ns<\/td>\n<td>1842812 ns<\/td>\n<\/tr>\n<tr>\n<td>go-astar<\/td>\n<td>453939 ns<\/td>\n<td>939300 ns<\/td>\n<td>1032581 ns<\/td>\n<\/tr>\n<tr>\n<td>tile<\/td>\n<td>107632 ns<\/td>\n<td>169613 ns<\/td>\n<td>182342 ns<\/td>\n<\/tr>\n<tr>\n<td>grid<\/td>\n<td>1816039 ns<\/td>\n<td>1154117 ns<\/td>\n<td>1189989 ns<\/td>\n<\/tr>\n<tr>\n<td>paths<\/td>\n<td>6588751 ns<\/td>\n<td>5158604 ns<\/td>\n<td>6114856 <abbr title=\"\u041d\u0430\u043d\u043e\u0441\u0435\u043a\u0443\u043d\u0434\u044b; 6114856 ns - \u044d\u0442\u043e ~0.006 \u0441\u0435\u043a\u0443\u043d\u0434 \u0438\u043b\u0438 ~6.1 ms\">ns<\/abbr><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0441\u043a\u0440\u043e\u043c\u043d\u043e\u0433\u043e \u043f\u043e\u043b\u044f \u0432 50&#215;50 \u043a\u043b\u0435\u0442\u043e\u043a \u044d\u0442\u043e \u043f\u043b\u043e\u0445\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b.<\/p>\n<p>  <\/p>\n<p>\u0410 \u0447\u0442\u043e \u0442\u0430\u043c \u043f\u043e \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u0438\u044e \u043f\u0430\u043c\u044f\u0442\u0438?<\/p>\n<p>  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u0411\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430<\/th>\n<th>\u0422\u0435\u0441\u0442 no_walls<\/th>\n<th>\u0422\u0435\u0441\u0442 simple_wall<\/th>\n<th>\u0422\u0435\u0441\u0442 multi_wall<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>astar<\/td>\n<td>337336 B<\/td>\n<td>511908 B<\/td>\n<td>722690 B<\/td>\n<\/tr>\n<tr>\n<td>go-astar<\/td>\n<td>43653 B<\/td>\n<td>93122 B<\/td>\n<td>130731 B<\/td>\n<\/tr>\n<tr>\n<td>tile<\/td>\n<td>123118 B<\/td>\n<td>32950 B<\/td>\n<td>65763 B<\/td>\n<\/tr>\n<tr>\n<td>grid<\/td>\n<td>996889 <abbr title=\"\u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u0431\u0430\u0439\u0442\u0430\u0445; 996889 \u0431\u0430\u0439\u0442 - \u044d\u0442\u043e \u043f\u043e\u0447\u0442\u0438 \u043c\u0435\u0433\u0430\u0431\u0430\u0439\u0442!\">B<\/abbr><\/td>\n<td>551976 B<\/td>\n<td>740523 B<\/td>\n<\/tr>\n<tr>\n<td>paths<\/td>\n<td>235168 B<\/td>\n<td>194768 B<\/td>\n<td>230416 B<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u044f\u0437\u044b\u043a\u0435: \u0442\u043e \u0430\u043b\u043b\u043e\u0446\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e. \u041f\u0430\u043c\u044f\u0442\u0438 \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u043d\u043e\u0433\u043e, \u043d\u043e \u043c\u043e\u0436\u0435\u0442 \u0445\u043e\u0442\u044f \u0431\u044b \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u0442\u0438\u0445 \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u043d\u0435\u0432\u0435\u043b\u0438\u043a\u043e?<\/p>\n<p>  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u0411\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430<\/th>\n<th>\u0422\u0435\u0441\u0442 no_walls<\/th>\n<th>\u0422\u0435\u0441\u0442 simple_wall<\/th>\n<th>\u0422\u0435\u0441\u0442 multi_wall<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>astar<\/td>\n<td>2008<\/td>\n<td>3677<\/td>\n<td>3600<\/td>\n<\/tr>\n<tr>\n<td>go-astar<\/td>\n<td>529<\/td>\n<td>1347<\/td>\n<td>1557<\/td>\n<\/tr>\n<tr>\n<td>tile<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>grid<\/td>\n<td>2976<\/td>\n<td>1900<\/td>\n<td>1759<\/td>\n<\/tr>\n<tr>\n<td>paths<\/td>\n<td>7199<\/td>\n<td>6368<\/td>\n<td>7001<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  <\/p>\n<p>\u041f\u0440\u0438\u044f\u0442\u043d\u043e \u0443\u0434\u0438\u0432\u043b\u044f\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e <a href=\"https:\/\/github.com\/kelindar\/tile\" rel=\"nofollow noopener noreferrer\">kelindar\/tile<\/a>, \u043d\u043e \u043a \u043d\u0435\u043c\u0443 \u043c\u044b \u0435\u0449\u0451 \u0432\u0435\u0440\u043d\u0451\u043c\u0441\u044f.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043b\u0435 \u0441\u0431\u043e\u0440\u0430 \u044d\u0442\u0438\u0445 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u044f \u0441\u0442\u0430\u043b \u0443\u0432\u0435\u0440\u0435\u043d, \u0447\u0442\u043e \u0441\u043c\u043e\u0433\u0443 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435. \u042d\u0442\u0438\u043c \u043c\u044b \u0438 \u0437\u0430\u0439\u043c\u0451\u043c\u0441\u044f: \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0441\u0430\u043c\u0443\u044e \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0443\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438 \u043d\u0430 Go.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0414\u0435\u0442\u0430\u043b\u0438 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u043e\u0432 \u0434\u043b\u044f \u043d\u0435\u0440\u0434\u043e\u0432<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<hr\/>\n<p>  <\/p>\n<p>\u0425\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0441\u0442\u0438\u043a\u0438 \u043c\u0430\u0448\u0438\u043d\u044b, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u043b\u0438\u0441\u044c \u0437\u0430\u043c\u0435\u0440\u044b:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">OS: Linux Mint 21.1 CPU: x86-64 12th Gen Intel(R) Core(TM) i5-1235U Tools used: \u201cgo test -bench\u201d, benchstat Turbo boost: disabled (intel_pstate\/no_turbo=1) Go version: devel go1.21-c30faf9c54<\/code><\/pre>\n<p>  <\/p>\n<p>\u0411\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u043b\u0438\u0441\u044c \u0447\u0435\u0440\u0435\u0437 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 <code>go test bench -benchmem<\/code>, \u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043b\u0438\u0441\u044c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e <a href=\"https:\/\/github.com\/quasilyte\/qbenchstat\" rel=\"nofollow noopener noreferrer\">qbenchstat<\/a>.<\/p>\n<p>  <\/p>\n<hr\/>\n<\/div><\/div>\n<p>  <\/p>\n<p>\u041f\u0435\u0440\u0432\u044b\u043c \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0435\u043c\u044b\u043c \u043d\u0430\u043c\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0431\u0443\u0434\u0435\u0442 greedy BFS, \u0442\u0430\u043a \u043a\u0430\u043a \u0434\u043b\u044f \u043d\u0435\u0433\u043e \u044f \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b \u0431\u043e\u043b\u044c\u0448\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439, \u0430 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u0432 \u0441\u0430\u043c\u043e\u043c \u043a\u043e\u043d\u0446\u0435.<\/p>\n<p>  <\/p>\n<p>\u0411\u043e\u043b\u044c\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u0432\u043b\u0438\u044f\u043d\u0438\u044f \u043d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u041c\u0430\u0442\u0440\u0438\u0446\u0430 <abbr title=\"\u041a\u0430\u043a\u0438\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u044b, \u0430 \u043a\u0430\u043a\u0438\u0435 \u0437\u0430\u0431\u043b\u043e\u043a\u0438\u0440\u043e\u0432\u0430\u043d\u044b\">\u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438<\/abbr><\/li>\n<li>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438<\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Priority_queue\" rel=\"nofollow noopener noreferrer\">Priority queue<\/a> \u0434\u043b\u044f <abbr title=\"\u041e\u0447\u0435\u0440\u0435\u0434\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u0434\u043b\u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u044f\">frontier<\/abbr><\/li>\n<li>\u0410\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043f\u043e\u0441\u0435\u0449\u0451\u043d\u043d\u044b\u0445 \u043a\u043b\u0435\u0442\u043e\u043a<\/li>\n<\/ul>\n<p>  <\/p>\n<h2 id=\"matrica-prohodimosti\">\u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438<\/h2>\n<p>  <\/p>\n<p>\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0431\u0443\u0434\u0435\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c <abbr title=\"Cell\">\u043a\u043b\u0435\u0442\u043a\u0430\u043c\u0438<\/abbr>. \u0423 \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0435\u0441\u0442\u044c \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0430 \u0432\u043d\u0443\u0442\u0440\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">type GridCoord struct {   X int   Y int }<\/code><\/pre>\n<p>  <\/p>\n<p>Grid map \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u0442 \u0440\u0435\u043b\u044c\u0435\u0444 \u043c\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438. \u0412 \u0441\u0430\u043c\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0432\u0438\u0434\u0435 \u043a\u0430\u0436\u0434\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430 \u0445\u0440\u0430\u043d\u0438\u0442 <abbr title=\"Enum\">\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435-\u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435<\/abbr> \u0442\u0430\u0439\u043b\u0430.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">type CellType int  \/\/ \u0423 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435\u0433\u043e \u0442\u0440\u0438 \u0432\u0438\u0434\u0430 \u0442\u0430\u0439\u043b\u043e\u0432. const (   CellPlain CellType = iota \/\/ 0   CellSand                  \/\/ 1   CellLava                  \/\/ 2 )<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0440\u0438 \u0442\u0430\u0439\u043b\u0430 \u043c\u043e\u0436\u043d\u043e \u0443\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0432 \u0434\u0432\u0430 \u0431\u0438\u0442\u0430. \u0415\u0441\u043b\u0438 \u043a\u0430\u0436\u0434\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430 \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0432\u0441\u0435\u0433\u043e \u0434\u0432\u0430 \u0431\u0438\u0442\u0430, \u0442\u043e\u0433\u0434\u0430 \u043a\u0430\u0440\u0442\u0430 \u0438\u0437 3600 (60&#215;60) \u043a\u043b\u0435\u0442\u043e\u043a \u0431\u0443\u0434\u0435\u0442 \u0432\u0435\u0441\u0438\u0442\u044c 900 \u0431\u0430\u0439\u0442.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">type Grid struct {   numCols uint   numRows uint    \/\/ \u0425\u0440\u0430\u043d\u0438\u043c \u043f\u043e 4 \u043a\u043b\u0435\u0442\u043a\u0438 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0431\u0430\u0439\u0442\u0435.   bytes []byte }<\/code><\/pre>\n<p>  <\/p>\n<p>\u0414\u043e\u0441\u0442\u0443\u043f \u043a \u0438\u043d\u0434\u0438\u0432\u0438\u0434\u0443\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0435 \u0431\u0443\u0434\u0435\u0442 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u044c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func (g *Grid) GetCellTile(c GridCoord) uint8 {   x := uint(c.X)   y := uint(c.Y)   if x >= g.numCols || y >= g.numRows {     return 0 \/\/ \u041a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0430 \u043b\u0435\u0436\u0438\u0442 \u0432\u043d\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b   }   i := y*g.numCols + x   byteIndex := i \/ 4   shift := (i % 4) * 2   return (g.bytes[byteIndex] >> shift) &amp; 0b11 }<\/code><\/pre>\n<p>  <\/p>\n<blockquote><p>\u0414\u0435\u043b\u0435\u043d\u0438\u0435 \u043d\u0430 \u043c\u043d\u043e\u0433\u0438\u0435 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438, \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u043e\u043c, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0437\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043d\u0435 \u043f\u0435\u0440\u0435\u0436\u0438\u0432\u0430\u0439\u0442\u0435.<\/p><\/blockquote>\n<p>\u0420\u0430\u0437\u043d\u044b\u0435 \u0432\u0438\u0434\u044b \u044e\u043d\u0438\u0442\u043e\u0432 \u043c\u043e\u0433\u0443\u0442 \u0438\u043c\u0435\u0442\u044c \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0438 \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f. \u041a\u0442\u043e-\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e \u0440\u0430\u0432\u043d\u0438\u043d\u0435, \u0434\u0440\u0443\u0433\u0438\u0435 \u0435\u0449\u0451 \u0438 \u043f\u043e \u043f\u0443\u0441\u0442\u044b\u043d\u0435, \u0430 \u043b\u0435\u0442\u0443\u043d\u044b \u043c\u043e\u0433\u0443\u0442 \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u0442\u044c \u0434\u0430\u0436\u0435 \u043b\u0430\u0432\u0443.<\/p>\n<p>  <\/p>\n<p>\u0421\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u043c\u0443 Grid&#8217;\u0443 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0438 \u2014 \u043f\u0435\u0440\u0435\u0440\u0430\u0441\u0445\u043e\u0434 \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u0434\u0443\u0431\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u0432 \u0438\u0441\u0442\u0438\u043d\u044b.<\/p>\n<p>  <\/p>\n<p>\u0412\u0432\u0435\u0434\u0451\u043c \u043f\u043e\u043d\u044f\u0442\u0438\u0435 <abbr title=\"Layer\">\u0441\u043b\u043e\u044f<\/abbr>. \u0421\u043b\u043e\u0439 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u043f\u0440\u0435\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0435\u0439 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u044f. \u0422\u0430\u043a \u043a\u0430\u043a \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0438\u043c\u0435\u044e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u0442 0 \u0434\u043e 3, \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0447\u0435\u0442\u044b\u0440\u0435 \u043a\u043b\u044e\u0447\u0430.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">type GridLayer [4]byte  \/\/ i - \u044d\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043a\u043b\u0435\u0442\u043a\u0438, \u043e\u0442 0 \u0434\u043e 3. func (l GridLayer) Get(i int) byte {   return l[i] }<\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u0442 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u043e\u043c \u043d\u0435\u044f\u0432\u043d\u043e\u0433\u043e <abbr title=\"\u0410\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u0430\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u043d\u0430 \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0445\">bound check<\/abbr> \u043c\u043e\u0436\u043d\u043e \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f:<\/p>\n<p>  <\/p>\n<pre><code class=\"diff\">- return l[i] + return l[i &amp; 0b11]<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0440\u0430\u0441\u0448\u0438\u0440\u044f\u0442\u044c \u0434\u0432\u0430 \u0431\u0438\u0442\u0430 \u0432 \u043e\u0434\u0438\u043d \u0431\u0430\u0439\u0442. \u0414\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c\u0441\u044f, \u0447\u0442\u043e \u043d\u0443\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u2014 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0435 \u043f\u0440\u043e\u0445\u043e\u0434\u0430. \u041b\u044e\u0431\u043e\u0435 \u0434\u0440\u0443\u0433\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f greedy BFS \u0431\u0443\u0434\u0435\u0442 \u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u044f \u0441 \u0446\u0435\u043d\u043e\u0439 1, \u0430 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u0432\u0435\u0441\u0430 \u0431\u0443\u0434\u0443\u0442 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 <code>A*<\/code>.<\/p>\n<p>  <\/p>\n<p>\u0421\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0441\u043b\u043e\u0438 \u0434\u043b\u044f \u0440\u0430\u0437\u043d\u044b\u0445 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0439 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u044f:<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">var NormalLayer = pathing.GridLayer{   CellPlain: 1, \/\/ \u041f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u043e   CellSand:  0, \/\/ \u041d\u0435\u043b\u044c\u0437\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f   CellLava:  0, \/\/ \u041d\u0435\u043b\u044c\u0437\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f }  var FlyingLayer = pathing.GridLayer{   CellPlain: 1, \/\/ \u041f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u043e   CellSand:  1, \/\/ \u041f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u043e   CellLava:  1, \/\/ \u041f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u043e }<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e\u0438\u0441\u043a \u043f\u0443\u0442\u0438 \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043d\u0435 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e, \u0430 \u043f\u043e\u0441\u043b\u0435 \u0438\u0445 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f \u0447\u0435\u0440\u0435\u0437 \u0441\u043b\u043e\u0439. \u0421\u043b\u043e\u0439 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u0434\u0430\u0432\u0430\u0442\u044c \u043d\u0430 \u0432\u0445\u043e\u0434 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043f\u0443\u0442\u0438.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u0430 \u044d\u0442\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b:<\/p>\n<p>  <\/p>\n<ul>\n<li>2 \u0431\u0438\u0442\u0430 \u043d\u0430 \u043a\u043b\u0435\u0442\u043a\u0443<\/li>\n<li>\u0421 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u043b\u043e\u0451\u0432 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0434\u043d\u0443 \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0434\u043b\u044f \u0440\u0430\u0437\u043d\u044b\u0445 \u044e\u043d\u0438\u0442\u043e\u0432<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u041f\u043e\u043c\u0438\u043c\u043e \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e\u0439 \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0438 \u043f\u0430\u043c\u044f\u0442\u0438, \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0434\u0440\u0443\u0436\u0431\u0443 \u0441 \u043a\u044d\u0448-\u043b\u0438\u043d\u0438\u044f\u043c\u0438. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u044d\u0448 \u043b\u0438\u043d\u0438\u0438 \u0440\u0430\u0432\u0435\u043d 64 \u0431\u0430\u0439\u0442\u0430\u043c. \u041f\u0430\u0442\u0442\u0435\u0440\u043d\u044b \u0434\u043e\u0441\u0442\u0443\u043f\u0430 \u043a \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0442\u0430\u043a\u043e\u0432\u044b, \u0447\u0442\u043e \u0432\u0441\u0435\u0433\u0434\u0430 \u0438\u0437\u0432\u043b\u0435\u043a\u0430\u044e\u0442\u0441\u044f \u0441\u043e\u0441\u0435\u0434\u0438 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043a\u043b\u0435\u0442\u043e\u0447\u043a\u0438. \u041a\u043b\u0435\u0442\u043a\u0438 \u0441\u043b\u0435\u0432\u0430 \u0438 \u0441\u043f\u0440\u0430\u0432\u0430 \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u0440\u044f\u0434\u043e\u043c, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0434\u0430\u0436\u0435 \u0432 \u0440\u0430\u043c\u043a\u0430\u0445 \u0442\u043e\u0433\u043e \u0436\u0435 \u0431\u0430\u0439\u0442\u0430. \u041a\u043b\u0435\u0442\u043a\u0430 \u043d\u0438\u0436\u0435 \u0438 \u0432\u044b\u0448\u0435 \u0431\u0443\u0434\u0443\u0442 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u044c \u0447\u0442\u0435\u043d\u0438\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0441\u0442\u0440\u043e\u043a \u043c\u0430\u0442\u0440\u0438\u0446\u044b. \u0427\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u043c\u044b \u0442\u0440\u0430\u0442\u0438\u043c \u043d\u0430 \u043a\u043b\u0435\u0442\u043a\u0443, \u0442\u0435\u043c \u0432\u044b\u0448\u0435 \u0448\u0430\u043d\u0441, \u0447\u0442\u043e <code>2*numCols<\/code> \u044f\u0447\u0435\u0435\u043a \u043e\u043a\u0430\u0436\u0443\u0442\u0441\u044f \u0432\u043d\u0443\u0442\u0440\u0438 \u043e\u0434\u043d\u043e\u0439 \u043a\u044d\u0448-\u043b\u0438\u043d\u0438\u0438.<\/p>\n<p>  <\/p>\n<blockquote><p>\u0417\u0434\u0435\u0441\u044c \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0431\u044b \u0435\u0449\u0451 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Z-order_curve\" rel=\"nofollow noopener noreferrer\">Morton order<\/a>. \u0412 \u0442\u0435\u043e\u0440\u0438\u0438, \u044d\u0442\u043e \u043c\u043e\u0433\u043b\u043e \u0431\u044b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f \u0431\u043e\u043b\u0435\u0435 cache-friendly, \u0445\u043e\u0442\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0447\u0442\u0435\u043d\u0438\u044f \u0441\u0442\u0430\u043b\u0430 \u0431\u044b \u0431\u043e\u043b\u0435\u0435 \u0434\u043e\u0440\u043e\u0433\u043e\u0439.<\/p><\/blockquote>\n<p>  <\/p>\n<h2 id=\"reprezentaciya-puti\">\u0420\u0435\u043f\u0440\u0435\u0437\u0435\u043d\u0442\u0430\u0446\u0438\u044f \u043f\u0443\u0442\u0438<\/h2>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/9y\/wv\/hs\/9ywvhsghv7fwj26gay0l4j2bysu.png\" data-src=\"https:\/\/habrastorage.org\/webt\/9y\/wv\/hs\/9ywvhsghv7fwj26gay0l4j2bysu.png\"\/><\/p>\n<p>  <\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0438\u0434\u0443\u0442 \u043f\u043e \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0438\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e\u043c\u0443 \u043f\u0443\u0442\u0438 (\u0445\u0435-\u0445\u0435) \u2014 \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043a\u0430\u043a \u043d\u0430\u0431\u043e\u0440\u0430 \u0442\u043e\u0447\u0435\u043a.<\/p>\n<p>  <\/p>\n<p>\u0412\u043e\u0437\u044c\u043c\u0451\u043c \u0434\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u044d\u0442\u0443 \u043a\u0430\u0440\u0442\u0443:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/1q\/v0\/sl\/1qv0slvupxky481i39z9k49kxw0.png\" data-src=\"https:\/\/habrastorage.org\/webt\/1q\/v0\/sl\/1qv0slvupxky481i39z9k49kxw0.png\"\/><\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 \u043f\u0443\u0442\u0438 \u043e\u0442 {0,1} \u043a {2,3} \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0442\u0430\u043a\u043e\u0439 \u043d\u0430\u0431\u043e\u0440 \u0442\u043e\u0447\u0435\u043a:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">{0,0} {1,0} {2,0} {2,1} {2,2} {2,3}<\/code><\/pre>\n<p>  <\/p>\n<p>\u0410 \u0432\u043e\u0442 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u0436\u0435 \u043f\u0443\u0442\u044c:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">Up Right Right Down Down Down<\/code><\/pre>\n<p>  <\/p>\n<p>\u041d\u0430\u043c \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0438\u0437 \u0447\u0435\u0442\u044b\u0440\u0451\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439:<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">type Direction int  const (   DirRight Direction = iota   DirDown   DirLeft   DirUp )<\/code><\/pre>\n<p>  <\/p>\n<p>\u0423\u0436\u0435 \u0434\u043e\u0433\u0430\u0434\u0430\u043b\u0438\u0441\u044c, \u0447\u0442\u043e \u043f\u0440\u043e\u0438\u0437\u043e\u0439\u0434\u0451\u0442 \u0434\u0430\u043b\u044c\u0448\u0435? 4 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u2014 \u0434\u0432\u0430 \u0431\u0438\u0442\u0430.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/g_\/bv\/ix\/g_bvixdflizisyhmn9la7zeg4k4.png\" data-src=\"https:\/\/habrastorage.org\/webt\/g_\/bv\/ix\/g_bvixdflizisyhmn9la7zeg4k4.png\"\/><\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a \u043a\u0430\u043a \u043a\u0430\u0436\u0434\u044b\u0439 \u0448\u0430\u0433 \u043d\u0430\u0441\u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u0435\u043d, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0432 uint64 \u0446\u0435\u043b\u044b\u0445 32 \u0448\u0430\u0433\u0430. \u042d\u0442\u043e\u0433\u043e \u043d\u0430\u043c \u043d\u0435 \u0445\u0432\u0430\u0442\u0438\u0442, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432\u043e\u0437\u044c\u043c\u0451\u043c \u043f\u0430\u0440\u0443 uint64. \u0412\u043c\u0435\u0441\u0442\u043e 64 \u0448\u0430\u0433\u043e\u0432 \u043c\u044b \u0441\u043c\u043e\u0436\u0435\u043c \u0443\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e 56, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0434\u0432\u0430 \u0431\u0430\u0439\u0442\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0440\u0435\u0437\u0435\u0440\u0432\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0434 \u043f\u0430\u0440\u0443 \u0441\u043b\u0443\u0436\u0435\u0431\u043d\u044b\u0445 \u043f\u043e\u043b\u0435\u0439 \u0438\u0442\u0435\u0440\u0430\u0442\u043e\u0440\u0430 \u043f\u0443\u0442\u0438.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">const (   gridPathBytes  = (16 - 2)          \/\/ \u0414\u0432\u0430 \u0431\u0430\u0439\u0442\u0430 \u0441\u043b\u0443\u0436\u0435\u0431\u043d\u044b\u0445   gridPathMaxLen = gridPathBytes * 4 \/\/ 56 )  type GridPath struct {   bytes [gridPathBytes]byte   len   byte   pos   byte }<\/code><\/pre>\n<p>  <\/p>\n<p>GridPath \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 16 \u0431\u0430\u0439\u0442, \u0430 \u0432 \u043f\u0430\u043c\u044f\u0442\u0438 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/pi\/ve\/y_\/pivey_7a9yecdoxiupp_cuzkhbo.png\" data-src=\"https:\/\/habrastorage.org\/webt\/pi\/ve\/y_\/pivey_7a9yecdoxiupp_cuzkhbo.png\"\/><\/p>\n<p>  <\/p>\n<p>\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u0443\u0442\u0438 \u043d\u0435 \u0438\u043c\u0435\u044e\u0442 \u0441\u043c\u044b\u0441\u043b\u0430 \u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0430 \u0432\u043e\u0442 \u0435\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0448\u0430\u0433\u0438, \u0442\u043e \u043c\u044b \u043f\u0440\u0438\u0434\u0451\u043c \u043a \u0442\u043e\u0447\u043a\u0435 \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u0418\u0437-\u0437\u0430 \u044d\u0442\u043e\u0433\u043e \u044f \u043d\u0430\u0437\u044b\u0432\u0430\u044e \u044d\u0442\u0438 \u0448\u0430\u0433\u0438 \u0434\u0435\u043b\u044c\u0442\u0430\u043c\u0438.<\/p>\n<p>  <\/p>\n<p>\u0421\u0432\u043e\u0439\u0441\u0442\u0432\u0430 GridPath:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u041f\u0443\u0442\u0438 \u0434\u043b\u0438\u043d\u043e\u0439 \u0434\u043e 56 \u043a\u043b\u0435\u0442\u043e\u043a (\u0431\u0443\u0434\u0435\u0442 \u0432\u0430\u0436\u043d\u043e \u0434\u0430\u043b\u0435\u0435)<\/li>\n<li>\u041d\u0435 \u043d\u0443\u0436\u043d\u043e \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u0432 \u043a\u0443\u0447\u0435 \u2014 \u044d\u0442\u043e 16 \u0431\u0430\u0439\u0442\u043e\u0432 \u043d\u0430 \u0441\u0442\u0435\u043a\u0435 (\u0438\u043b\u0438 \u0432 \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u0430\u0445)<\/li>\n<li>Value-\u0441\u0435\u043c\u0430\u043d\u0442\u0438\u043a\u0430, \u043e\u0431\u044b\u0447\u043d\u043e\u0435 \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u043d\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0435 \u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0412 \u043d\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u0441\u0438\u044f\u0445 Go \u0432\u0441\u0451 \u0431\u043e\u043b\u044c\u0448\u0435 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0435\u0440\u0435\u0434\u0430\u044e\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u044b \u0438 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 Go tip \u0432 <a href=\"https:\/\/godbolt.org\/\" rel=\"nofollow noopener noreferrer\">godbolt<\/a> \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442 \u043e\u0434\u043d\u0443 \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044e <a href=\"https:\/\/www.felixcloutier.com\/x86\/movups\" rel=\"nofollow noopener noreferrer\">MOVUPS<\/a> \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0438 GridPath.<\/p>\n<p>  <\/p>\n<h2 id=\"ochered-s-prioritetami\">\u041e\u0447\u0435\u0440\u0435\u0434\u044c \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c\u0438<\/h2>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0432\u044b\u0431\u043e\u0440\u0430 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c\u0441\u044f \u0441 \u043d\u0430\u0431\u043e\u0440\u043e\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u0434\u0443\u0442 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b.<\/p>\n<p>  <\/p>\n<ul>\n<li><code>Push(coord, p)<\/code> \u2014 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0443 \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c<\/li>\n<li><code>Pop() -> (coord, p)<\/code> \u2014 \u0438\u0437\u0432\u043b\u0435\u0447\u044c \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0443 \u0441 <strong>\u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c<\/strong> p<\/li>\n<li><code>Reset()<\/code> \u2014 \u043e\u0447\u0438\u0441\u0442\u0438\u0442\u044c \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u0435\u0440\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u041f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 <code>p<\/code> \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0414\u043b\u044f greedy BFS \u044d\u0442\u043e <a href=\"https:\/\/en.wikipedia.org\/wiki\/Taxicab_geometry\" rel=\"nofollow noopener noreferrer\">Manhattan distance<\/a> \u043e\u0442 <code>coord<\/code> \u043a \u0444\u0438\u043d\u0438\u0448\u0443.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e \u044d\u0442\u043e\u043c\u0443 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044e \u043d\u0430\u043c \u043c\u043e\u0433\u043b\u0430 \u0431\u044b \u043f\u043e\u0434\u043e\u0439\u0442\u0438 minheap. \u0414\u043b\u044f <code>A*<\/code> \u043c\u044b \u0442\u0430\u043a \u0438 \u043f\u043e\u0441\u0442\u0443\u043f\u0438\u043c, \u043d\u043e greedy BFS \u043c\u043e\u0436\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0435\u0449\u0451 \u0441\u0438\u043b\u044c\u043d\u0435\u0435, \u0435\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c \u043e\u0441\u043e\u0431\u0443\u044e <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bucket_queue\" rel=\"nofollow noopener noreferrer\">bucket queue<\/a>. \u0415\u0451 \u0438 \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c.<\/p>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043a\u0430\u0436\u0434\u044b\u0439 &#171;\u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442&#187; \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c \u0431\u0430\u043a\u0435\u0442\u043e\u043c, \u0442\u043e\u0433\u0434\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432 \u0442\u0430\u043a\u043e\u0439 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u0438\u044f\u0442\u043d\u043e\u0435: \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a \u044d\u0442\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430.<\/p>\n<p>  <\/p>\n<p>\u0410 \u0432\u043e\u0442 \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u0431\u0430\u043a\u0435\u0442\u043d\u043e\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u0412 \u0441\u0430\u043c\u043e\u043c \u0431\u0430\u0437\u043e\u0432\u043e\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435 \u0432\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u0431\u0430\u043a\u0435\u0442\u044b \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043d\u0430\u0439\u0434\u0451\u0442\u0441\u044f \u043d\u0435\u043f\u0443\u0441\u0442\u043e\u0439. <abbr title=\"Dread Lord\">\u041b\u043e\u0440\u0434 \u0443\u0436\u0430\u0441\u0430<\/abbr> \u0438\u0437 WarCraft III \u0441\u043a\u0430\u0437\u0430\u043b \u0431\u044b: &#171;\u0414\u0443\u0440\u0430\u0446\u043a\u0438\u0439 \u043f\u043b\u0430\u043d.&#187;<\/p>\n<p>  <\/p>\n<p>\u0412\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043b\u0438\u043d\u0430 \u043f\u0443\u0442\u0438 \u0440\u0430\u0432\u043d\u0430 56. \u0422\u0430\u043a \u043a\u0430\u043a 56&lt;64, uint64 \u0445\u0432\u0430\u0442\u0438\u0442 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0432\u0441\u0435\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">type priorityQueue[T any] struct {   buckets [64][]T   mask    uint64 }<\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u0430:<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func (q *priorityQueue[T]) Push(priority int, value T) {   \/\/ \u0423\u0431\u0438\u0440\u0430\u0435\u043c bound check \u0447\u0435\u0440\u0435\u0437 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e &amp;, \u044d\u0442\u043e\u0442 \u0442\u0440\u044e\u043a \u0432\u044b \u0443\u0436\u0435 \u0432\u0438\u0434\u0435\u043b\u0438.   i := uint(priority) &amp; 0b111111   q.buckets[i] = append(q.buckets[i], value)   q.mask |= 1 &lt;&lt; i }<\/code><\/pre>\n<p>  <\/p>\n<p>\u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e, \u043c\u0430\u0441\u043a\u0430 \u0440\u0430\u0432\u043d\u0430 0. \u041f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0431\u0430\u043a\u0435\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u0431\u044b\u043b \u043f\u0443\u0441\u0442\u044b\u043c, \u0431\u0438\u0442 \u0432 \u043d\u0443\u0436\u043d\u043e\u043c \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0438 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u0432 1.<\/p>\n<p>  <\/p>\n<p>\u0418\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435, \u043d\u043e \u0442\u043e\u0436\u0435 \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0435:<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func (q *priorityQueue[T]) Pop() T {   \/\/ TrailingZeros64 \u043d\u0430 amd64 - \u044d\u0442\u043e \u043f\u0430\u0440\u0430 \u043c\u0430\u0448\u0438\u043d\u043d\u044b\u0445 \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0439 (BSF \u0438 CMOV).   \/\/ \u0417\u0430 \u044d\u0442\u0438 \u0434\u0432\u0435 \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 \u043c\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0439   \/\/ \u043d\u0430\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u043d\u0435\u043f\u0443\u0441\u0442\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430.   i := uint(bits.TrailingZeros64(q.mask))   if i &lt; uint(len(q.buckets)) {     \/\/ \u042d\u0442\u0438 \u0434\u0432\u0438 \u0441\u0442\u0440\u043e\u0447\u043a\u0438 \u0438\u0437\u0432\u043b\u0435\u043a\u0430\u044e\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0437 \u0431\u0430\u043a\u0435\u0442\u0430 (pop).     e := q.buckets[i][len(q.buckets[i])-1]     q.buckets[i] = q.buckets[i][:len(q.buckets[i])-1]     if len(q.buckets[i]) == 0 {       \/\/ \u0415\u0441\u043b\u0438 \u0431\u0430\u043a\u0435\u0442 \u0441\u0442\u0430\u043b \u043f\u0443\u0441\u0442\u044b\u043c, \u0437\u0430\u043d\u0443\u043b\u044f\u0435\u043c \u043d\u0443\u0436\u043d\u044b\u0439 \u0431\u0438\u0442 \u0432 \u043c\u0430\u0441\u043a\u0435.       q.mask &amp;^= 1 &lt;&lt; i     }     return e   }    \/\/ \u041e\u0447\u0435\u0440\u0435\u0434\u044c \u043f\u0443\u0441\u0442\u0430\u044f, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c zero value.   var x T   return x }<\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c Reset. \u0421\u0430\u043c\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u2014 \u044d\u0442\u043e <abbr title=\"\u042d\u0442\u043e \u0442\u0435\u0440\u043c\u0438\u043d\u043e\u043b\u043e\u0433\u0438\u044f Go \u0434\u043b\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0442\u0438\u043f\u0430 std::vector::clear() \u0432 C++ \u0438 \u0447\u0435\u043c-\u0442\u043e \u043f\u043e\u0445\u043e\u0436 \u043d\u0430 ArrayList.clear() \u0432 Java\">\u0440\u0435\u0441\u043b\u0430\u0439\u0441\u0438\u043d\u0433<\/abbr> \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430. \u041f\u0430\u043c\u044f\u0442\u044c \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0430 \u0434\u043b\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f, \u0430 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0435\u0433\u043e \u0437\u0430\u043d\u0443\u043b\u0435\u043d\u0438\u044f \u043d\u0430\u043c \u0432\u0441\u0451 \u0440\u0430\u0432\u043d\u043e \u043d\u0435 \u043d\u0443\u0436\u043d\u043e.<\/p>\n<p>  <\/p>\n<p>\u041d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u043a \u0442\u0430\u043a\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f: \u043d\u0430\u043c \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0432\u0441\u0435\u0433\u0434\u0430 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0432\u0441\u0435 64 \u0431\u0430\u043a\u0435\u0442\u0430, \u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0438\u0437 \u043d\u0438\u0445 \u043f\u0443\u0441\u0442\u0430\u044f. \u0422\u0430\u043a \u043a\u0430\u043a \u0443 \u043d\u0430\u0441 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0431\u0438\u0442\u043e\u0432\u0430\u044f \u043c\u0430\u0441\u043a\u0430, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0435\u0439 \u0438 \u0437\u0434\u0435\u0441\u044c.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func (q *priorityQueue[T]) Reset() {   mask := q.mask   \/\/ \u041d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043e\u0447\u0438\u0449\u0435\u043d\u0438\u0435 \u0441 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043d\u0435\u043f\u0443\u0441\u0442\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430,   \/\/ \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u044f \u0432\u0441\u0435 \u043f\u0443\u0441\u0442\u044b\u0435 \"\u0441\u043f\u0440\u0430\u0432\u0430\".   offset := uint(bits.TrailingZeros64(mask))   mask >>= offset   i := offset   \/\/ \u041a\u043e\u0433\u0434\u0430 \"\u0441\u043b\u0435\u0432\u0430\" \u043e\u0442 \u043e\u043a\u043d\u0430 \u0432\u0441\u0435 \u0431\u0430\u043a\u0435\u0442\u044b \u0431\u0443\u0434\u0443\u0442 \u043f\u0443\u0441\u0442\u044b\u043c\u0438, \u0446\u0438\u043a\u043b \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u0442\u0441\u044f.   for mask != 0 {     if i &lt; uint(len(q.buckets)) {       q.buckets[i] = q.buckets[i][:0]     }     mask >>= 1     i++   }   q.mask = 0 }<\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u0441\u043e\u0431\u0430\u044f \u043c\u0430\u0433\u0438\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u0443\u0441\u0442\u043e\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 Reset \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u0440\u0435\u0441\u043b\u0430\u0439\u0441\u0438\u043d\u0433 0 \u0440\u0430\u0437. \u0414\u043b\u044f \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430 \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043b\u0438\u0448\u044c \u0435\u0433\u043e. \u0414\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0439\u0442\u0438 \u043e\u043a\u043d\u043e \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438.<\/p>\n<p>  <\/p>\n<p>\u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0431\u043e\u043d\u0443\u0441\u0430, \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u043a\u0430\u043a \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e IsEmpty:<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func (q *priorityQueue[T]) IsEmpty() bool {   return q.mask == 0 }<\/code><\/pre>\n<p>  <\/p>\n<p>\u0418 \u043a\u0430\u043a \u043f\u043e\u0441\u043b\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0435 \u043b\u044e\u0431\u0438\u0442\u044c \u043f\u0430\u043a\u0435\u0442 <a href=\"https:\/\/pkg.go.dev\/math\/bits\" rel=\"nofollow noopener noreferrer\">math\/bits<\/a>?<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/h6\/va\/kt\/h6vaktdgkxeptiyrmo6ahzkurrs.png\" data-src=\"https:\/\/habrastorage.org\/webt\/h6\/va\/kt\/h6vaktdgkxeptiyrmo6ahzkurrs.png\"\/><\/p>\n<p>  <\/p>\n<h2 id=\"hranenie-poseschyonnyh-koordinat\">\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043f\u043e\u0441\u0435\u0449\u0451\u043d\u043d\u044b\u0445 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442<\/h2>\n<p>  <\/p>\n<p>\u0421\u0435\u043c\u0430\u043d\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u0430 <code>map[GridCoord]T<\/code>, \u0442\u043e\u043b\u044c\u043a\u043e \u0431\u044b\u0441\u0442\u0440\u0430\u044f \u0438 \u0441 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u043d\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c.<\/p>\n<p>  <\/p>\n<p>GridCoord \u2014 \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043f\u043e\u043b\u0435\u0439, \u043d\u043e \u0435\u0451 \u043c\u043e\u0436\u043d\u043e \u0443\u0436\u0430\u0442\u044c \u0434\u043e \u043e\u0434\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func packCoord(numCols int, c GridCoord) uint {   return uint((c.Y * numCols) + c.X) }<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0430\u043a \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043b\u0438\u043d\u0430 \u043f\u0443\u0442\u0438 \u0440\u0430\u0432\u043d\u0430 56, \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438 \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u043d\u0435 \u0432\u044b\u0439\u0434\u0435\u0442 \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044b \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0430 56*2+1. \u0415\u0441\u043b\u0438 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u0438\u0437 \u0433\u043b\u043e\u0431\u0430\u043b\u044c\u043d\u044b\u0445 \u0432 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0435, \u0442\u043e \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u044b\u0439 packCoord \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u0435\u043d <code>[0-12544]<\/code>.<\/p>\n<p>  <\/p>\n<p>\u042d\u0442\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u043a\u0440\u043e\u043c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u043b\u044e\u0447\u0435\u0439, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u0433\u043e\u043b\u043e\u0432\u0443 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 <abbr title=\"\u0422\u0430\u043a \u0432 Go \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b, \u0442\u0438\u043f\u0430 std::vector \u0438 ArrayList. \u0415\u0441\u043b\u0438 \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u0438\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c\u0438, \u0432\u0430\u043c \u0441\u0440\u0430\u0437\u0443 \u0436\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u044f\u0442, \u043f\u043e\u0447\u0435\u043c\u0443 \u0432\u044b \u043d\u0435 \u043f\u0440\u0430\u0432\u044b\">\u0441\u043b\u0430\u0439\u0441<\/abbr>, \u0433\u0434\u0435 \u043a\u043b\u044e\u0447\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u044f\u043c\u043e\u0439 \u0438\u043d\u0434\u0435\u043a\u0441. \u0423 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0431\u0443\u0434\u0435\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043c\u0438\u043d\u0443\u0441 \u2014 Reset \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u0437\u0430\u043d\u0443\u043b\u0435\u043d\u0438\u044f \u0441\u043b\u0430\u0439\u0441\u0430.<\/p>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c \u0432\u043c\u0435\u0441\u0442\u043e \u0441\u043b\u0430\u0439\u0441\u0430 <a href=\"https:\/\/research.swtch.com\/sparse\" rel=\"nofollow noopener noreferrer\">sparse map<\/a>, \u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 Reset \u0437\u0430 \u0441\u0447\u0451\u0442 \u0431\u043e\u043b\u0435\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u044b\u0445 Get \u0438 Set.<\/p>\n<p>  <\/p>\n<p>\u041b\u0443\u0447\u0448\u0435\u0435 \u043e\u0442 \u0434\u0432\u0443\u0445 \u043c\u0438\u0440\u043e\u0432 \u0432 \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u0434\u0430\u0451\u0442 <a href=\"https:\/\/habr.com\/ru\/articles\/762984\/\">generations map<\/a>, \u043e \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u044f \u043d\u0435\u0434\u0430\u0432\u043d\u043e \u043f\u0438\u0441\u0430\u043b \u043d\u0430 \u0425\u0430\u0431\u0440\u0435. \u042d\u0442\u0443 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0432\u044b\u0431\u0435\u0440\u0435\u043c.<\/p>\n<p>  <\/p>\n<h2 id=\"a-chto-tam-so-zvezdochkoy\">\u0410 \u0447\u0442\u043e \u0442\u0430\u043c \u0441\u043e \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u043e\u0439?<\/h2>\n<p>  <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0432\u0440\u0430\u0442\u0438\u0442\u044c greedy BFS \u0432 <code>A*<\/code> \u043d\u0430\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u0414\u0432\u0435 generations map \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u0434\u043d\u043e\u0439<\/li>\n<li>Min heap \u0432\u043c\u0435\u0441\u0442\u043e bucket queue<\/li>\n<li>\u041d\u0435\u043c\u043d\u043e\u0433\u043e \u0434\u0440\u0443\u0433\u0430\u044f \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0430 \u0434\u043b\u044f <code>p<\/code><\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0431\u0443\u0434\u0435\u0442 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0446\u0435\u043d\u0443 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u044f (\u043d\u0430\u043c \u044d\u0442\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0441\u0442\u043e\u0438\u0442).<\/p>\n<p>  <\/p>\n<p>\u041a\u043e\u0434 \u0442\u0430\u043c \u043d\u0435\u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043f\u043e\u0445\u043e\u0436\u0438\u0439, \u043d\u043e \u044f \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u044e \u0434\u0435\u043b\u0430\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u044f\u0445, \u0442\u0430\u043a \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u043b\u0438\u0448\u043d\u0438\u0445 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439 \u0438\/\u0438\u043b\u0438 \u0438\u043d\u0434\u0438\u0440\u0435\u043a\u0446\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u043e\u0439 \u0438 greedy bfs \u0434\u043b\u044f \u0432\u0430\u0448\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0438? \u041f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 <code>A*<\/code> \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0435\u0434\u043f\u043e\u0447\u0442\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u043c, \u043d\u043e greedy bfs \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 \u0440\u0430\u0431\u043e\u0447\u0435\u0439 \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<p>  <\/p>\n<p>Greedy BFS \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0447\u0430\u0441\u0442\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0447\u0442\u0438 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c, \u0445\u043e\u0442\u044f \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u043c\u043e\u0436\u0435\u0442 \u0435\u0433\u043e \u0440\u0430\u0441\u0441\u0442\u0440\u043e\u0438\u0442\u044c. \u0412 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u043a\u043e\u0433\u0434\u0430 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u0430 \u0438 greedy BFS \u043e\u0431\u0430 \u043d\u0430\u0445\u043e\u0434\u044f\u0442 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0443\u0442\u0438, \u043e\u0431\u044b\u0447\u043d\u043e \u043e\u043d\u0438 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u044d\u0442\u043e \u0432 \u0438\u0433\u0440\u0435, \u043c\u043e\u0436\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u043c\u0435\u043d\u0435\u0435 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0443\u0435\u043c\u044b\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u044b \u0434\u043b\u044f \u044e\u043d\u0438\u0442\u043e\u0432: \u0447\u0430\u0441\u0442\u044c \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u043e\u0432 \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0447\u0435\u0440\u0435\u0437 <code>A*<\/code>, \u0430 \u0434\u0440\u0443\u0433\u0443\u044e \u2014 \u0447\u0435\u0440\u0435\u0437 greedy BFS.<\/p>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0438\u0437 <a href=\"https:\/\/www.redblobgames.com\/pathfinding\/a-star\/introduction.html\" rel=\"nofollow noopener noreferrer\">\u043c\u043e\u0435\u0439 \u043b\u044e\u0431\u0438\u043c\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438<\/a>, \u0442\u043e greedy BFS \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0432\u0430\u0442\u044c \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043d\u0438\u0436\u0435. \u041e\u0434\u043d\u0430\u043a\u043e \u043c\u043e\u0439 greedy BFS \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441\u043b\u0435\u0433\u043a\u0430 \u0438\u043d\u0430\u0447\u0435 \u0438, \u043d\u0430 \u043c\u043e\u0438\u0445 \u0442\u0435\u0441\u0442\u0430\u0445 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0441\u0435\u0431\u044f \u0432\u0435\u0441\u044c\u043c\u0430 \u043d\u0435\u043f\u043b\u043e\u0445\u043e. \u0412\u0441\u0435\u0433\u043e \u0432 \u043f\u0430\u0440\u0435 \u0442\u0435\u0441\u0442\u043e\u0432 greedy BFS \u0441\u0442\u0440\u043e\u0438\u043b \u043c\u0435\u043d\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442, \u0447\u0435\u043c <code>A*<\/code>:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/cz\/37\/ek\/cz37ekjgxumblm8laebdrpukf0y.png\" data-src=\"https:\/\/habrastorage.org\/webt\/cz\/37\/ek\/cz37ekjgxumblm8laebdrpukf0y.png\"\/><\/p>\n<p>  <\/p>\n<h2 id=\"pobezhdaem-v-benchmarkah\">\u041f\u043e\u0431\u0435\u0436\u0434\u0430\u0435\u043c \u0432 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0430\u0445<\/h2>\n<p>  <\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0432\u0441\u0435 \u0440\u0435\u0446\u0435\u043f\u0442\u044b \u0432\u044b\u0448\u0435, \u0441\u043e\u0431\u0438\u0440\u0430\u0435\u043c <a href=\"https:\/\/github.com\/quasilyte\/pathing\/\" rel=\"nofollow noopener noreferrer\">\u0441\u0432\u043e\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438<\/a>.<\/p>\n<p>  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u0411\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430<\/th>\n<th>\u0422\u0435\u0441\u0442 no_walls<\/th>\n<th>\u0422\u0435\u0441\u0442 simple_wall<\/th>\n<th>\u0422\u0435\u0441\u0442 multi_wall<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><b>pathing<\/b><\/td>\n<td><b>3525<\/b> ns<\/td>\n<td><b>6353<\/b> ns<\/td>\n<td><b>16927<\/b> ns<\/td>\n<\/tr>\n<tr>\n<td><b>pathing A*<\/b><\/td>\n<td><b>20140<\/b> ns<\/td>\n<td><b>35846<\/b> ns<\/td>\n<td><b>44756<\/b> ns<\/td>\n<\/tr>\n<tr>\n<td>astar<\/td>\n<td>948367 ns<\/td>\n<td>1554290 ns<\/td>\n<td>1842812 ns<\/td>\n<\/tr>\n<tr>\n<td>go-astar<\/td>\n<td>453939 ns<\/td>\n<td>939300 ns<\/td>\n<td>1032581 ns<\/td>\n<\/tr>\n<tr>\n<td>tile<\/td>\n<td>107632 ns<\/td>\n<td>169613 ns<\/td>\n<td>182342 ns<\/td>\n<\/tr>\n<tr>\n<td>grid<\/td>\n<td>1816039 ns<\/td>\n<td>1154117 ns<\/td>\n<td>1189989 ns<\/td>\n<\/tr>\n<tr>\n<td>paths<\/td>\n<td>6588751 ns<\/td>\n<td>5158604 ns<\/td>\n<td>6114856 ns<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  <\/p>\n<p>pathing \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 paths \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0432 2000 \u0440\u0430\u0437! <code>A*<\/code> \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0449\u0443\u0442\u0438\u043c\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 greedy BFS, \u043d\u043e \u0432\u0441\u0451 \u0435\u0449\u0451 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0439.<\/p>\n<p>  <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0438:<\/p>\n<p>  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u0411\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430<\/th>\n<th>\u0422\u0435\u0441\u0442 no_walls<\/th>\n<th>\u0422\u0435\u0441\u0442 simple_wall<\/th>\n<th>\u0422\u0435\u0441\u0442 multi_wall<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><b>pathing<\/b><\/td>\n<td><b>0<\/b><\/td>\n<td><b>0<\/b><\/td>\n<td><b>0<\/b><\/td>\n<\/tr>\n<tr>\n<td><b>pathing A*<\/b><\/td>\n<td><b>0<\/b><\/td>\n<td><b>0<\/b><\/td>\n<td><b>0<\/b><\/td>\n<\/tr>\n<tr>\n<td>astar<\/td>\n<td>2008<\/td>\n<td>3677<\/td>\n<td>3600<\/td>\n<\/tr>\n<tr>\n<td>go-astar<\/td>\n<td>529<\/td>\n<td>1347<\/td>\n<td>1557<\/td>\n<\/tr>\n<tr>\n<td>tile<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>grid<\/td>\n<td>2976<\/td>\n<td>1900<\/td>\n<td>1759<\/td>\n<\/tr>\n<tr>\n<td>paths<\/td>\n<td>7199<\/td>\n<td>6368<\/td>\n<td>7001<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  <\/p>\n<p>\u0422\u0430\u043a \u043a\u0430\u043a \u0432\u0441\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0435 \u043c\u043d\u043e\u0439, \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u044e\u0442 \u043f\u043e\u043b\u043d\u043e\u0435 \u043f\u0435\u0440\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438, \u043c\u0435\u0436\u0434\u0443 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435\u043c \u043f\u0443\u0442\u0435\u0439 \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442. \u041e\u0431\u044a\u0435\u043a\u0442 \u043f\u0443\u0442\u0438 \u0442\u043e\u0436\u0435 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432\u043e\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u044f \u0430\u043b\u043b\u043e\u043a\u0430\u0442\u043e\u0440\u0430.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u043b\u043e\u0441\u044c \u0432 \u0442\u044b\u0441\u044f\u0447\u0438 \u0440\u0430\u0437 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438 \u0431\u0435\u0437 \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0439 (zero alloc). \u041e\u043d\u043e \u0442\u043e\u0433\u043e \u0441\u0442\u043e\u0438\u043b\u043e.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0420\u0430\u0437\u0431\u043e\u0440 kelindar\/tile (\u043e\u043f\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e!)<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<hr\/>\n<p>  <\/p>\n<p>\u0412 <a href=\"https:\/\/github.com\/kelindar\/tile\" rel=\"nofollow noopener noreferrer\">kelindar\/tile<\/a> \u043c\u044b \u0443\u0432\u0438\u0434\u0435\u043b\u0438 \u043b\u044e\u0431\u043e\u043f\u044b\u0442\u043d\u044b\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b: \u0432\u0441\u0435\u0433\u043e 3 \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0438, \u0430 \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u043e \u043f\u0440\u0438 \u044d\u0442\u043e\u043c ~100000 \u0431\u0430\u0439\u0442\u043e\u0432. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f.<\/p>\n<p>  <\/p>\n<p>\u0414\u043b\u044f frontier \u0442\u0430\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f <a href=\"https:\/\/github.com\/kelindar\/tile\/blob\/28d6c88c33465e7826873b7107ca27894d62cad4\/path.go#L151\" rel=\"nofollow noopener noreferrer\">\u043a\u0430\u0441\u0442\u043e\u043c\u043d\u044b\u0439 heap<\/a>. \u0412\u043c\u0435\u0441\u0442\u043e \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u043e\u0433\u043e \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437, \u0430\u0432\u0442\u043e\u0440 <a href=\"https:\/\/github.com\/kelindar\/tile\/blob\/28d6c88c33465e7826873b7107ca27894d62cad4\/path.go#L127\" rel=\"nofollow noopener noreferrer\">\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442<\/a> <code>sync.Pool<\/code> \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f. \u041e\u0442\u0441\u044e\u0434\u0430 \u043c\u0430\u043b\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u0439 \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u2014 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u044b \u043f\u0435\u0440\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f.<\/p>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0442\u0430\u0439\u043b\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f <a href=\"https:\/\/github.com\/kelindar\/tile\/blob\/28d6c88c33465e7826873b7107ca27894d62cad4\/grid.go#L183\" rel=\"nofollow noopener noreferrer\">\u0441\u0442\u0440\u0430\u043d\u0438\u0446\u044b \u0438\u0437 \u0431\u043b\u043e\u043a\u043e\u0432 3\u04453<\/a>. \u0417\u0432\u0443\u0447\u0438\u0442 \u043b\u044e\u0431\u043e\u043f\u044b\u0442\u043d\u043e, \u043d\u043e \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u044b\u0438\u0433\u0440\u044b\u0448 \u043e\u0442 \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u043a\u0430 \u043d\u0435 \u044f\u0441\u0435\u043d, \u043d\u0430\u0434\u043e \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c. \u041f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0438\u043d\u0443\u0441 \u044d\u0442\u043e\u0439 \u0441\u0445\u0435\u043c\u044b \u2014 \u043e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u0432\u044b\u0437\u044b\u0432\u0430\u0442\u044c \u043b\u0438\u0448\u043d\u044e\u044e \u0440\u0430\u0431\u043e\u0442\u0443 \u0441 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u043e\u0439 <a href=\"https:\/\/github.com\/kelindar\/tile\/blob\/28d6c88c33465e7826873b7107ca27894d62cad4\/grid.go#L123\" rel=\"nofollow noopener noreferrer\">\u0441\u0440\u0430\u0437\u0443 \u0442\u0440\u0451\u0445 &#171;\u0441\u0442\u0440\u0430\u043d\u0438\u0446&#187;<\/a>.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0432 map, \u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0451\u0442\u0441\u044f \u043e\u043d\u0430 \u0441 \u0440\u0430\u0437\u0443\u043c\u043d\u043e\u0439 <a href=\"https:\/\/github.com\/kelindar\/tile\/blob\/28d6c88c33465e7826873b7107ca27894d62cad4\/path.go#L76\" rel=\"nofollow noopener noreferrer\">\u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u043a\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u0430<\/a>: \u03c0r^2. \u0422\u0430\u043a \u0430\u0432\u0442\u043e\u0440 \u0432 \u0443\u0434\u0430\u0447\u043d\u043e\u043c \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442 \u043b\u0438\u0448\u044c \u043e\u0434\u043d\u0443 \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u044e \u0434\u043b\u044f map, \u043d\u043e \u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u043e\u0433\u0440\u043e\u043c\u043d\u043e\u0439 (\u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u0432\u0441\u0435\u0433\u0434\u0430 \u0434\u043b\u044f \u0445\u0443\u0434\u0448\u0435\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f).<\/p>\n<p>  <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u0432\u0438\u0434\u0435 \u0441\u043b\u0430\u0439\u0441\u0430 \u0442\u043e\u0447\u0435\u043a, \u043e\u0442\u0441\u044e\u0434\u0430 \u0435\u0449\u0451 \u043e\u0434\u043d\u0430 \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u044f.<\/p>\n<p>  <\/p>\n<hr\/>\n<\/div><\/div>\n<p>  <\/p>\n<h2 id=\"vyvody\">\u0412\u044b\u0432\u043e\u0434\u044b<\/h2>\n<p>  <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432\u0430\u0436\u043d\u044b, \u043e\u0434\u043d\u0430\u043a\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u2014 \u0442\u043e\u0436\u0435. \u0418\u043d\u043e\u0433\u0434\u0430 \u0441\u0435\u0440\u0438\u044f \u043c\u0438\u043a\u0440\u043e\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439 \u0432\u0435\u0434\u0451\u0442 \u043a \u0444\u0435\u043d\u043e\u043c\u0435\u043d\u0430\u043b\u044c\u043d\u043e\u043c\u0443 \u044d\u0444\u0444\u0435\u043a\u0442\u0443.<\/p>\n<p>  <\/p>\n<p>\u0423 \u043c\u043e\u0435\u0439 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438 \u0435\u0441\u0442\u044c \u0434\u0432\u0430 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043b\u0438\u043d\u0430 \u043f\u0443\u0442\u0438 \u2014 56 \u0448\u0430\u0433\u043e\u0432<\/li>\n<li>\u041d\u0430 \u043e\u0434\u043d\u043e\u0439 \u043a\u0430\u0440\u0442\u0435 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e 4 \u0432\u0438\u0434\u0430 \u0442\u0430\u0439\u043b\u043e\u0432 (2 \u0431\u0438\u0442\u0430)<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u041e\u0434\u043d\u0430\u043a\u043e \u0441 \u043d\u0438\u043c\u0438 \u043c\u043e\u0436\u043d\u043e \u0436\u0438\u0442\u044c:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u0427\u0430\u0441\u0442\u0438\u0447\u043d\u044b\u0435 \u043f\u0443\u0442\u0438 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u0442\u044c \u0432 \u043e\u0434\u0438\u043d<\/li>\n<li>\u041e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0435 enum&#8217;\u044b \u0434\u043b\u044f \u0431\u0438\u043e\u043c\u043e\u0432 \u043c\u043e\u0433\u0443\u0442 \u043e\u0442\u043b\u043e\u0436\u0438\u0442\u044c \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u041f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u0430\u0441\u044c \u0441\u0442\u0430\u0442\u044c\u044f? \u0423 \u043d\u0430\u0441 \u0432 <a href=\"https:\/\/t.me\/go_gamedev\" rel=\"nofollow noopener noreferrer\">\u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u0435 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0438\u0433\u0440 \u043d\u0430 Go<\/a> \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u0435\u0441\u0435\u043b\u043e! \u041f\u0440\u0438\u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0439\u0442\u0435\u0441\u044c, \u0431\u0443\u0434\u0435\u043c \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u0438\u0433\u0440\u0443\u0448\u043a\u0438 \u043d\u0430 \u043d\u0430\u0448\u0435\u043c \u043b\u044e\u0431\u0438\u043c\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0432\u043c\u0435\u0441\u0442\u0435.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0435\u0437\u043d\u044b\u0435 \u0441\u0441\u044b\u043b\u043a\u0438:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u0418\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u0438: <a href=\"https:\/\/github.com\/quasilyte\/pathing\/\" rel=\"nofollow noopener noreferrer\">github.com\/quasilyte\/pathing<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=X8C-R-jDkG4\" rel=\"nofollow noopener noreferrer\">\u0417\u0430\u043f\u0438\u0441\u044c \u0434\u043e\u043a\u043b\u0430\u0434\u0430 \u043d\u0430 \u044d\u0442\u0443 \u0442\u0435\u043c\u0443<\/a><\/li>\n<li><a href=\"https:\/\/research.swtch.com\/sparse\" rel=\"nofollow noopener noreferrer\">\u0420\u0430\u0437\u0431\u043e\u0440 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b sparse map \u043e\u0442 Russ Cox<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/articles\/762984\/\">\u0420\u0430\u0437\u0431\u043e\u0440 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b generations map \u043e\u0442 \u043c\u0435\u043d\u044f<\/a><\/li>\n<li><a href=\"https:\/\/github.com\/quasilyte\/roboden-game\" rel=\"nofollow noopener noreferrer\">\u0418\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u0438 \u0438\u0433\u0440\u044b Roboden<\/a><\/li>\n<li><a href=\"https:\/\/factorio.com\/blog\/post\/fff-317\" rel=\"nofollow noopener noreferrer\">\u041f\u043e\u0441\u0442 \u043e \u043f\u043e\u0438\u0441\u043a\u0435 \u043f\u0443\u0442\u0438 \u0432 Factorio<\/a><\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/766882\/\"> https:\/\/habr.com\/ru\/articles\/766882\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432\u0430\u0436\u043d\u044b. \u041d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0438\u0445 \u043c\u043e\u0436\u043d\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043e-\u0440\u0430\u0437\u043d\u043e\u043c\u0443.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0438 \u043e\u0434\u043d\u043e\u043c \u0438 \u0442\u043e\u043c \u0436\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u0432 \u0442\u044b\u0441\u044f\u0447\u0443 \u0440\u0430\u0437 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043d\u0430\u0438\u0432\u043d\u043e\u0439.<\/p>\n<p>  <\/p>\n<p>\u041b\u044e\u0431\u0438\u0442\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0442\u0440\u044e\u043a\u0438 \u0441 \u0431\u0438\u0442\u0430\u043c\u0438? \u0422\u043e\u0433\u0434\u0430 \u0441\u043a\u043e\u0440\u0435\u0435 \u043f\u043e\u0434 \u043a\u0430\u0442!<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/nn\/wj\/8m\/nnwj8mo5yr20jfueyowen6u-pbw.png\" data-src=\"https:\/\/habrastorage.org\/webt\/nn\/wj\/8m\/nnwj8mo5yr20jfueyowen6u-pbw.png\"\/><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-357275","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/357275","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=357275"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/357275\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=357275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=357275"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=357275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}