WC3
Добавлен Koladik,
опубликован
Алгоритмы, Наработки и Способности
Способ реализации:
vJass
Тип:
Алгоритм
Версия Warcraft:
1.31+
Введение
Данный алгоритм позволяет создать квазислучайное распределение. То есть позволяет создать случайное распределение точек, минимальное расстояние между которыми фиксированно, но тем не менее само распределение точек сохраняет свойства случайного. Например это нужно, для того, что бы случайное появление баз в или героев имело минимальное расстояние между собой, чтобы всегда имелось расстояние между ними. Алгоритм быстрый, так как занимает время O(N), где N число точек распределения.
Используемые библиотеки
Данная реализация использует четыре дополнительные библиотеки. Две опубликованные.
И три мои неопубликованные.
Библиотека математики
mathlib
library MathLib initializer onInit
struct math
static method ln takes real x returns real
local real y
local real dy
local integer n = 1
set x = x - 1
set dy = x
set y = dy
loop
set n = n + 1
set dy = -1*dy*x/I2R(n*(n-1))
set y = y + dy
exitwhen (RAbsBJ(dy) < 0.0001)
endloop
return y
endmethod
static method floor takes real r returns integer
if( r >= 0) then
return R2I(r)
else
return R2I(r - 1)
endif
endmethod
static method rabs takes real a returns real
if (a >= 0) then
return a
else
return -a
endif
endmethod
static method exp takes real x returns real
local integer k = 1
local real Ox = 1
local real y = Ox
loop
set Ox = Ox*x/k
set y = y + Ox
set k = k + 1
exitwhen(math.rabs(Ox) < 0.001)
endloop
return y
endmethod
static method factorial takes integer k returns integer
local integer i = 0
local integer m = 1
loop
set i = i + 1
set m = m*i
exitwhen (i == k)
endloop
return m
endmethod
static method isgn takes integer x returns integer
if (x > 0) then
return 1
else
return -1
endif
endmethod
static method rsgn takes real x returns real
if (x > 0) then
return 1.
else
return -1.
endif
endmethod
static method rmax takes real x1, real x2 returns real
if(x1 > x2)then
return x1
else
return x2
endif
endmethod
static method rhoL2 takes real x1, real y1, real x2, real y2 returns real
local real x = x1 - x2
local real y = y1 - y2
return SquareRoot(x*x + y*y)
endmethod
static method rhoL1 takes real x1, real y1, real x2, real y2 returns real
return math.rabs(x1 - x2) + math.rabs(y1 - y2)
endmethod
static method rhoL0 takes real x1, real y1, real x2, real y2 returns real
return math.rmax(math.rabs(x1 - x2), math.rabs(y1 - y2))
endmethod
private static method onInit takes nothing returns nothing
//Заглушка
endmethod
endstruct
endlibraryБиблиотека массивов, расширяющая возможности Multidimensional Array v1.2b by AGD
numjusslib
library numjuss initializer onInit uses MultidimensionalArray
globals
//private hashtable hash
endglobals
struct nj
static method empty_I2D takes integer shape_x, integer shape_y returns nj_I2D
return nj_I2D.create(shape_x, shape_y)
endmethod
static method fill_I2D takes integer shape_x, integer shape_y, integer value returns nj_I2D
local nj_I2D this = nj_I2D.create(shape_x, shape_y)
call this.fill.execute(value)
return this
endmethod
static method zeros_I2D takes integer shape_x, integer shape_y returns nj_I2D
return nj.fill_I2D(shape_x, shape_y, 0)
endmethod
endstruct
struct nj_I1D
integer shape_x
private Integer1D ar
method operator []= takes integer idx, integer value returns nothing
set this.ar[idx] = value
endmethod
method operator [] takes integer idx returns integer
return this.ar[idx]
endmethod
method append takes integer value returns nothing
set this[shape_x] = value
set this.shape_x = this.shape_x + 1
endmethod
static method create takes integer shape_x returns nj_I1D
local nj_I1D this = thistype.allocate()
set this.ar = Integer1D.create()
set this.shape_x = shape_x
return this
endmethod
endstruct
struct nj_I2D extends Integer2D
integer shape_x
integer shape_y
method fill takes integer value returns nothing
local integer i
local integer j
set i = 0
loop
exitwhen(i == this.shape_x)
set j = 0
loop
exitwhen(j == this.shape_y)
set this[i][j] = value
set j = j + 1
endloop
set i = i + 1
endloop
endmethod
method print takes nothing returns nothing
local string s_col = ""
local integer i
local integer j
local texttag loc_tt = CreateTextTag()
set i = 0
loop
exitwhen(i == shape_x)
set j = 0
loop
exitwhen(j == shape_y)
set s_col = s_col + I2S(this[i][j]) + " "
set j = j + 1
endloop
call BJDebugMsg(s_col)
set s_col = ""
set i = i + 1
endloop
endmethod
static method create takes integer shape_x, integer shape_y returns nj_I2D
local nj_I2D this = Integer2D.create()
set this.shape_x = shape_x
set this.shape_y = shape_y
return this
endmethod
endstruct
private function onInit takes nothing returns nothing
//local nj_I2D A = nj.zeros_I2D(255,255)
//call BJDebugMsg("Все")
endfunction
endlibraryБиблиотека управления сеткой карты, продолжающая расширять возможности двумерных массивов, привязывающая ячейки сетки к карте и имеющая функция преобразования ячеек массива в координаты и обратно.
matmaplib
library MatMapLib initializer onInit uses numjuss, MathLib, MultidimensionalArray
struct MatMap
integer DX
integer DY
nj_I2D map
method operator [] takes integer i returns Integer1D
return this.map[i]
endmethod
// ==== Свойства ====
method operator shape_x takes nothing returns integer
return this.map.shape_x
endmethod
method operator shape_y takes nothing returns integer
return this.map.shape_y
endmethod
static method operator maxX takes nothing returns integer
return R2I(GetRectMaxX(GetWorldBounds()))
endmethod
static method operator minX takes nothing returns integer
return R2I(GetRectMinX(GetWorldBounds()))
endmethod
static method operator maxY takes nothing returns integer
return R2I(GetRectMaxY(GetWorldBounds()))
endmethod
static method operator minY takes nothing returns integer
return R2I(GetRectMinY(GetWorldBounds()))
endmethod
//
method mat_i2x takes integer i returns real
return I2R((2*i+1)*this.DX/2 + thistype.minX)
endmethod
method mat_j2y takes integer j returns real
return thistype.maxY - I2R(2*j+1)*this.DY/2
endmethod
method mat_x2i takes real x returns integer
return math.floor((x - thistype.minX)/this.DX)
endmethod
method mat_y2j takes real y returns integer
return math.floor((thistype.maxY - y)/this.DY)
endmethod
static method create takes integer shape_x, integer shape_y returns thistype
local thistype this = thistype.allocate()
set this.DX = (thistype.maxX - thistype.minX)/shape_x
set this.DY = (thistype.maxY - thistype.minY)/shape_y
set this.map = nj.zeros_I2D(shape_x, shape_y)
return this
endmethod
static method create_fill takes integer shape_x, integer shape_y, integer value returns thistype
local thistype this = thistype.allocate()
set this.DX = (thistype.maxX - thistype.minX)/shape_x
set this.DY = (thistype.maxY - thistype.minY)/shape_y
set this.map = nj.fill_I2D(shape_x, shape_y, value)
return this
endmethod
static method create_grid takes integer dx, integer dy returns thistype
local thistype this = thistype.allocate()
local integer shape_x = (thistype.maxX - thistype.minX)/dx
local integer shape_y = (thistype.maxY - thistype.minY)/dy
set this.DX = dx
set this.DY = dy
set this.map = nj.zeros_I2D(shape_x, shape_y)
return this
endmethod
static method create_small takes nothing returns thistype
return thistype.create_grid(128,128)
endmethod
static method create_medium takes nothing returns thistype
return thistype.create_grid(256,256)
endmethod
static method create_large takes nothing returns thistype
return thistype.create_grid(512,512)
endmethod
static method onInit takes nothing returns nothing
//Заглушка
endmethod
endstruct
endlibraryОписание алгоритма
Данный алгоритм представляет собой реализацию в vJass алгоритма Бридсона для двумерного пространства.
Начальные параметры. Минимальное расстояние между точками real r. Число integer K попыток генерации точек вокруг каждой точки распределения. Область которой будет генерироваться алгоритм rect rec.
- Шаг инициализации Инициализируем два массива для сохранения координат точек распределения по x и по y. Инициализируем целочисленную матрицу, соответствующую ячейкам сетки для сохранения номера массива и ускорения пространственного поиска. Выбираем размер ячейки сетки равный r/sqrt(n), так, что каждая ячейка содержит не более одной точки распределения, так как диагональ квадрата сетки равна r . -1 указывает на то, что ячейка не содержит точек распределения, а неотрицательное значение указывает на индекс экземпляра, расположенного в ячейке.
- Шаг первый Генерируем начальную точку, случайно, в области генерации rec. И вносим ее в сетку и в активный лист.
- Шаг второй Выберем индекс из массива точек распределения из активного листа, скажем i-й. сгенерируем k точек случайно выбранных равномерно в кольце между радиусом r и 2r вокруг x_i точки, проверяем находится ли она в пределах расстояния r существующих точек распределения, используя сетку, что бы проверять только ближайшие точки, а не все. Если точка достаточно далеко от существующих экземпляров внедрять ее в массив точек распределения и добавляем ее в активный лист. После генерации k точек, удаляем x_i из активного листа.
- Шаг третий повторяем второй шаг пока не закончится активный лист.
Результат
Код алгоритма
QuasiGaussLib
library QuasiRandom uses MatMapLib, MathLib
private struct RB
MatMap map
nj_I1D xar
nj_I1D yar
rect rec
integer K
real R
method operator minX takes nothing returns integer
return R2I(GetRectMinX(this.rec))
endmethod
method operator minY takes nothing returns integer
return R2I(GetRectMinY(this.rec))
endmethod
method operator maxX takes nothing returns integer
return R2I(GetRectMaxX(this.rec))
endmethod
method operator maxY takes nothing returns integer
return R2I(GetRectMaxY(this.rec))
endmethod
static method create takes real R, integer K, rect rec returns thistype
local thistype this = thistype.allocate()
local location loc
local real x1
local real y1
//
set this.K = K
set this.R = R
set this.xar = nj_I1D.create(0)
set this.yar = nj_I1D.create(0)
set this.map = GridCreate(R)
set this.rec = rec
return this
endmethod
method GenerateLocation takes real x0, real y0, real r returns location
local real xi_r = r*SquareRoot(GetRandomReal(0, 1)) + r
local real xi_phi = GetRandomReal(0, 2*bj_PI)
local real x = xi_r*Cos(xi_phi) + x0
local real y = xi_r*Sin(xi_phi) + y0
if(this.minX < x and x < this.maxX and /*
*/ this.minY < y and y < this.maxY)then
return Location(x, y)
else
return null
endif
endmethod
method GetFirst takes nothing returns location
local integer x = GetRandomInt(this.minX, this.maxX)
local integer y = GetRandomInt(this.minY, this.maxY)
return Location(I2R(x), I2R(y))
endmethod
static method GridCreate takes real r returns MatMap
local real DX = r/SquareRoot(2)
local real DY = r/SquareRoot(2)
local integer nx = math.floor(I2R(MatMap.maxX - MatMap.minX)/DX)+1
local integer ny = math.floor(I2R(MatMap.maxY - MatMap.minY)/DY)+1
return MatMap.create_fill(nx, ny, -1)
endmethod
method AddPointAnyWay takes real x, real y returns nothing
local integer i = this.map.mat_x2i(x)
local integer j = this.map.mat_y2j(y)
set this.map[i][j] = this.xar.shape_x
call this.xar.append(R2I(x))
call this.yar.append(R2I(y))
endmethod
method CheckCellFromPoint takes real x, real y, integer i, integer j returns boolean
local real rho
local integer k2
if(not(/*
*/ 0 <= i and i < this.map.shape_x and /*
*/ 0 <= j and j < this.map.shape_y))then
return true
endif
set k2 = this.map[i][j]
if (k2 != -1) then
set rho = math.rhoL2(x, y, I2R(this.xar[k2]),I2R(this.yar[k2]))
if (rho < this.R) then
return false
else
return true
endif
else
return true
endif
endmethod
method firststep takes nothing returns nothing
local location loc = this.GetFirst()
local real x1 = GetLocationX(loc)
local real y1 = GetLocationY(loc)
call RemoveLocation(loc)
call this.AddPointAnyWay(x1, y1)
endmethod
method generatefor takes integer k1 returns nothing
local integer k2
local location loc
local real x1 = this.xar[k1]
local real y1 = this.yar[k1]
local real x2
local real y2
local integer i
local integer j
local boolean bool
local real rho
set k2 = 0
loop
exitwhen(k2 == this.K)
set loc = GenerateLocation(x1, y1, this.R)
if(loc != null)then
set x2 = GetLocationX(loc)
set y2 = GetLocationY(loc)
set i = map.mat_x2i(x2)
set j = map.mat_y2j(y2)
if (map[i][j] == -1) then
set bool = true
if(/*
*/ not(this.CheckCellFromPoint(x2, y2, i-1, j )) or /*
*/ not(this.CheckCellFromPoint(x2, y2, i-1, j+1)) or /*
*/ not(this.CheckCellFromPoint(x2, y2, i, j+1)) or /*
*/ not(this.CheckCellFromPoint(x2, y2, i+1, j+1)) or /*
*/ not(this.CheckCellFromPoint(x2, y2, i+1, j )) or /*
*/ not(this.CheckCellFromPoint(x2, y2, i+1, j-1)) or /*
*/ not(this.CheckCellFromPoint(x2, y2, i, j-1)) or /*
*/ not(this.CheckCellFromPoint(x2, y2, i-1, j-1))) then
set bool = false
endif
if(bool)then
call this.AddPointAnyWay(x2, y2)
endif
endif
call RemoveLocation(loc)
endif
set k2 = k2 + 1
endloop
endmethod
method step takes integer k1 returns integer
local integer i = this.xar.shape_x
call generatefor.execute(k1)
return this.xar.shape_x - i
endmethod
static method Gen takes real R, integer K, rect rec returns thistype
local thistype this = thistype.create(R, K, rec)
local integer j = 0
call this.firststep()
loop
exitwhen(j == this.xar.shape_x)
call this.step(j)
set j = j + 1
endloop
return this
endmethod
static method onInit takes nothing returns nothing
endmethod
endstruct
struct QR
nj_I1D xar
nj_I1D yar
static method create takes real R, integer K, rect rec returns thistype
local thistype this = thistype.allocate()
local RB rb = RB.Gen(R, K, rec)
set this.xar = rb.xar
set this.yar = rb.yar
return this
endmethod
endstruct
endlibraryИспользование API
library TestQR initializer onInit
private function Test takes QR qr returns nothing
local integer i = 0
call BJDebugMsg("Найдено точек " + I2S(qr.xar.shape_x))
loop
exitwhen(i == qr.xar.shape_x)
call CreateUnit(Player(0),'hfoo', qr.xar[i], qr.yar[i], 0)
set i = i + 1
endloop
endfunction
private function onInit takes nothing returns nothing
local QR qr = QR.create(1024.0, 10, GetPlayableMapRect())
call Test(qr)
endfunction
endlibraryФункция local QR qr = QR.create(1024.0, 10, GetPlayableMapRect()) заполняет область GetPlayableMapRect() точками, доступ к котрым осуществляется через qr.xar[i] и qr.yar[i] для координаты x и y соответственно. Размер массива можно узнать по команде qr.xar.shape_x
в результате получается следующее распределение точек
в результате получается следующее распределение точек
Общее число точек может отличатся от генерации к генерации. Карту пример можно скачать по ссылке
Тот же алгоритм но на питоне, писал, что бы разораться и легче перенести в war3. Может кому-то пригодится.
Python
import numpy as np
import math
import matplotlib as mpl
import matplotlib.pyplot as plt
from matplotlib.ticker import FixedLocator
class QuasiRand2d:
def getcirk(self,i,j):
array = [(i - 1, j),
(i - 1, j + 1),
(i, j + 1),
(i + 1, j + 1),
(i + 1, j),
(i + 1, j - 1),
(i, j - 1),
(i - 2, j),
(i, j + 2),
(i + 2, j),
(i, j - 2)]
return [self.grid[array[i]] for i in range(0,len(array)) if
0 <= array[i][0] < self.nx and
0 <= array[i][1] < self.ny]
def x2i(self, x):
return np.int32(np.floor((x - self.minX) / self.dx))
def y2j(self, y):
return np.int32(np.floor((y - self.minY) / self.dy))
def getsubarray(self, x0, y0, k=20):
r = self.r
grid = self.grid
R = r * np.sqrt(self.rng.random(size=k)) + r
phi = self.rng.random(size=k) * 2 * np.pi
X = []
Y = []
for i in range(0, k):
x = R[i] * np.cos(phi[i]) + x0
y = R[i] * np.sin(phi[i]) + y0
if(
self.minX <= x <= self.maxX and
self.minY <= y <= self.maxY):
X.append(x)
Y.append(y)
X = np.int32(np.array(X))
Y = np.int32(np.array(Y))
return X, Y
def expandarray(self, x0, y0, k=20):
X, Y = self.getsubarray(x0, y0, k)
I = self.x2i(X)
J = self.y2j(Y)
for i in range(0, len(I)):
if self.grid[I[i], J[i]] == -1:
b = True
for i2 in self.getcirk(I[i], J[i]):
if i2 != -1:
l = math.sqrt((self.X[i2] - X[i]) ** 2 + (self.Y[i2] - Y[i]) ** 2)
if l < self.r:
b = False
break
if b:
print(len(self.X))
self.grid[I[i], J[i]] = len(self.X)
self.X.append(X[i])
self.Y.append(Y[i])
def step(self):
imax = len(self.X)
for i in range(self.i, imax):
self.expandarray(self.X[i], self.Y[i], k=20)
self.i = imax
def __init__(self, minX, maxX, minY, maxY, r):
self.dx = r/math.sqrt(2)
self.dy = self.dx
self.r = r
self.minX = minX
self.minY = minY
self.maxX = maxX
self.maxY = maxY
self.rng = np.random.default_rng()
self.nx = int((maxX - minX)/self.dx)+1
self.ny = int((maxY - minY)/self.dy)+1
self.grid = np.full((self.nx, self.ny), -1, np.int32)
self.X = [np.int32(0)]#[self.rng.integers(int(maxX - minX), dtype=np.int32) + minX]
self.Y = [np.int32(0)]#[self.rng.integers(int(maxY - minY), dtype=np.int32) + minY]
self.grid[self.x2i(self.X[0]), self.y2j(self.Y[0])] = 0
self.i = 0
maxX = 512*34
maxY = 512*34
minX = -maxX
minY = -maxY
QR = QuasiRand2d(minX, maxX, minY, maxY, 512)
for i in range(0,40):
QR.step()
X = QR.X
Y = QR.Y
minorsX = np.arange(QR.minX, QR.maxX+1, QR.dx)
minorsY = np.arange(QR.minY, QR.maxY+1, QR.dy)
fig = plt.figure()
fig.set_size_inches(10, 6)
ax = fig.add_subplot(1, 1, 1)
ax.xaxis.set_minor_locator(FixedLocator(minorsX))
ax.yaxis.set_minor_locator(FixedLocator(minorsY))
ax.grid(which='minor', color='black', linestyle='-', linewidth = "0.5")
# im1 = ax.imshow(np.transpose(B))
# im1.set_cmap(cmap)
# im1.set_clim(0, cmap.N)
ax.plot(X,Y,'*')
ax.set_xlim((minX, maxX))
ax.set_ylim((minY, maxY))
plt.show()
`
ОЖИДАНИЕ РЕКЛАМЫ...
0
BrEd Pitt
1 месяц назад
0
За питоновый алгоритм отдельное спасибо! Даже не знал про такой способ генерации
Чтобы оставить комментарий, пожалуйста, войдите на сайт.