forum.boolean.name - Нужна помощь с ботами

forum.boolean.name (http://forum.boolean.name/index.php)

- 2D-программирование (http://forum.boolean.name/forumdisplay.php?f=13)

- - Нужна помощь с ботами (http://forum.boolean.name/showthread.php?t=16352)

Нужна помощь с ботами

Делаю 2д игру. И во время программирования ботов столкнулся с проблемой: они проникают сквозь здания. А как сделать по другому не знаю. Помогите.

Ответ: Нужна помощь с готоми

Покажи код. Мы ж не знаем как у тебя столкновения устроены.

Ответ: Нужна помощь с готоми

Цитата:

Сообщение от Nuprahtor (Сообщение 219830)

Поначалу так и подумал.

Ответ: Нужна помощь с готоми

В подобных случаях пишут "телепаты в отпуске" и не отвечают более на вопросы автора.

В подобных случаях ботов учат обходить препятствия при помощи алгоритмов "волна", "А*" ("А-звездочка", "A-star") и т.п. Определение препятствий можно возложить на артистов (моделлерами из не назовешь, а подходящего слова в русском/украинском языке я не вспоминаю пока :-P ), либо на простенький алгоритм. Вариантов алгоритма множество ;) Сам пробовал решив задачу "лабиринт", построить модель поведения тупого (буквально) бота. Получилось забавно =)

Собственно, задача:

Цитата:

Задается матрица 20x20(желательно из файла) позиции которой: 1 - клетка проходима, 0 - клетка непроходима. Необходимо найти и показать выход из лабиринта из указываемой точки. Выходом является любая граничная клетка.

Подсказка: для решения - копайте в сторону "волнового" алгоритма.

Ответ: Нужна помощь с готоми

А где копать?:(

Ответ: Нужна помощь с готоми

Цитата:

Сообщение от undertaker (Сообщение 219835)

А где копать?:(

В гугле или на булке.

Ответ: Нужна помощь с готоми

А алгоритм Дейкстры для таких случаев не подходит?

Ответ: Нужна помощь с готоми

Цитата:

Сообщение от AVL (Сообщение 219840)

А алгоритм Дейкстры для таких случаев не подходит?

А у него доросли руки реализовывать сложные алгоритмы?

Ответ: Нужна помощь с готоми

А зачем создавать вторую тему? В старой не помогли, в новой помогут? :)

Ответ: Нужна помощь с готоми

Цитата:

Сообщение от Nerd96 (Сообщение 219843)

А у него доросли руки реализовывать сложные алгоритмы?

Ну лично я алгоритм Дейкстры знаю, а вот A* и волновой - не разбирал. Они намного проще?

Ответ: Нужна помощь с готоми

И чем это алгоритм Дэйкстры сложнее Астара ?

Вопрос аффтару :
Телепаты нынче действительно на расхват... поэтому ты опиши проблемму полностью.
Вот я например не пойму в каком пространстве ты пытаешся сделать коллизии, если это платформер - то тут одно решение, если стратежка - то совершенно другое решение убережет тебя от готов. (+ спаси и сохрани +)

Ответ: Нужна помощь с готоми

a в принципе там и объяснять нечего. Делаю 2д зомби шутер(движок отдаленно похож на гта 1) есть боты,которые идут на координаты гг. Мне нужно сделать так, чтобы они не проникали(проходили) сквозь сдания.

Ответ: Нужна помощь с готоми

if (бот_идет) and (впереди_по_ходу_движения_бота_здание) then бот_поворачивает_пока_впереди_не_будет_свободно

Ответ: Нужна помощь с готоми

Вот взяли и испугали парня. Его интересовало векторное перемещение, а вы ему алгоритмами А* и Дейкстры голову забили. Люди добрые, нельзя же так.

Ответ: Нужна помощь с готоми

Цитата:

Сообщение от AVL (Сообщение 219887)

if (бот_идет) and (впереди_по_ходу_движения_бота_здание) then бот_поворачивает_пока_впереди_не_будет_свободно

Уж лучше задачкой "лабиринт" - боты не будут зря проникать в заведомо тупики ;)

Уважаемый ТС, рассказываю максимально детально:

1) есть у вас карта. Разбейте ее на клетки размером с игроков (зомби/гг/союзники) - сделайте матрицу размерами M*N, где M = map_width / player_size, N = map_height / player_size, player_size = (player_width > player_height) ? player_width : player_height.

2) Заполните эту матрицу следующим образом: если в клетке A[i][j] препятствие - A[i][j] = -1; иначе - A[i][j] = 0.

3) Возьмите клетку в тупике (так нужно) и сделайте ее некоей start_cell{x, y}.

4) Примените волновой алгоритм: задайте некую очередь q = {start_cell}. И переменную index = 1. В цикле "пока очередь не пуста" выполняем следующее:
а) current_cell = q.shift();
б) A[current_cell.x][current_cell.y] = index;
в) index = index + 1;
г) "если клетка A[i + 1][j] проходима - добавляем ее в очередь"
д) "если клетка A[i - 1][j] проходима - добавляем ее в очередь"
е) "если клетка A[i][j + 1] проходима - добавляем ее в очередь"
ж) "если клетка A[i][j - 1] проходима - добавляем ее в очередь"

*условие "если клетка проходима" равносильно "если в клетке число 0"

Таким образом получаем "лабиринт", заполненный либо числом -1, либо натуральным числом. Так, чтобы из клетки A'(x1, y1) добраться в клетку B'(x2, y2) необходимо:

а) выбрать "обратное направление хода" - от клетки с большим числом в матрице до клетки с меньшим числом в матрице. То есть, если A[x1][y1] > A[x2][y2], то искать путь будем от B' к A'.

б) начиная с клетки с большим числом в матрице, начинаем искать путь (алгоритм идентичен волновому):

очередь q = { start_cell }; очередь path = { };
while (!q.empty())
c = q.shift()
path.push(c)
if (A[c.x + 1][c.y] < A[c.x][c.y]) q.push({c.x + 1, c.y})
if (A[c.x - 1][c.y] < A[c.x][c.y]) q.push({c.x - 1, c.y})
if (A[c.x][c.y + 1] < A[c.x][c.y]) q.push({c.x, c.y + 1})
if (A[c.x][c.y - 1] < A[c.x][c.y]) q.push({c.x, c.y - 1})

В результате получим реверсивный путь - от точки назначения к точке исходной позиции. Заметьте, если исходной позиции соответствует большее число в матрице, то путь не реверсивен. Иначе - "разворачиваем" массив/очередь path.

А потом все просто - в path у вас будет набор пар (x, y) - по ним можно определить, куда (в центр какой клетки) направить тот или иной спрайт =)

Ответ: Нужна помощь с готоми

Цитата:

Сообщение от Nikich (Сообщение 219895)

Товарища интересовали коллизии/обход препятствий ;)

Ответ: Нужна помощь с готоми

Коллизия как раз решается векторным перемещением, обход препятствий его не интересовал. Можете ещё раз перечитать его посты.

Ответ: Нужна помощь с готоми

Вот тебе пример, тут и коллизии, и пики, чтобы определить, есть ли препятствие впереди и обойти его. CodeArchive тебе в помощь.

Код:

;use these globals to get the collision point between a circle and a line. 

Global LineCollisionX#

Global LineCollisionY#



Graphics 800,600,16,2

SetBuffer BackBuffer()



;Create lines at screen edges

LineNew(0,0,800,0)

LineNew(800,0,800,600)

LineNew(0,600,800,600)

LineNew(0,0,0,600)



;Create two Circles

CircleNew(100,100,20,0.4,0.2)

CircleNew(200,100,50,-0.2,0.3)



event=0

cline.cline=Null

Repeat

        Cls

                

        If MouseHit(2)

                

                CircleNew(Rnd(200,600),Rnd(100,500),Rnd(10,40),Rnd(-2,2),Rnd(-2,2))

        

        EndIf

        

        Select event

        

                Case 0

                        If MouseHit(1)

                                x1#=MouseX()

                                y1#=MouseY()

                                event=1

                                cline=LineNew(x1#,y1#,x1+10,y1)

                        EndIf

                Case 1

                                        

                        LineRecalc(cline,x1,y1,MouseX(),MouseY())

                        If MouseHit(1)

                                event=0

                        EndIf

                

        

        End Select

        

        ;Update and draw stuff

        CircleUpdate()

        PoofUpdate()



        CircleDraw()

        LineDraw()

        PoofDraw()

                        

        Text 400,10,"2D Collision Example by Jeppe Nielsen 2004",1,0

        Text 400,30,"Left mouse button to create lines",1,0

        Text 400,50,"Right mouse button to create more circles",1,0

        

        Flip

        

Until KeyDown(1)

End



Type cline



        Field x1#,y1#,x2#,y2#,nx#,ny#,ux#,uy#



End Type



Function LineNew.cline(x1#,y1#,x2#,y2#)



        l.cline=New cline

        

        LineRecalc(l,x1#,y1#,x2#,y2#)

        

        Return l



End Function



Function LineRecalc(l.cline,x1#,y1#,x2#,y2#)



        l\x1=x1

        l\y1=y1

        l\x2=x2

        l\y2=y2



        dx#=l\x2-l\x1

        dy#=l\y2-l\y1

        

        d#=Sqr(dx*dx+dy*dy)

        If d#<0.0001

                d#=0.0001

        EndIf

        

        l\ux=dx/d

        l\uy=dy/d

        

        l\nx#=l\uy

        l\ny#=-l\ux



End Function



Function LineDraw()



For l.cline=Each cline

        

        Color 255,255,255

        Line l\x1,l\y1,l\x2,l\y2

        

        Color 255,255,0

        ;Draw normal

        xm#=(l\x1+l\x2)/2.0

        ym#=(l\y1+l\y2)/2.0

        Line xm,ym,xm+l\nx*10,ym+l\ny*10

        

Next



End Function



;Global LineCollisionX#

;Global LineCollisionY#



;Returns the shortest distance from a point to a line

;Use LineCollisionX and LineCollisionY to get the collision point.

Function LineDistance#(l.cline,x#,y#)



        dx#=l\x2-l\x1

        dy#=l\y2-l\y1

        

        d#=Sqr(dx*dx+dy*dy)

        

        px#=l\x1-x#

        py#=l\y1-y#

        

        dist#=(dx*py-px*dy) / d

        

        LineCollisionX=x#-l\nx*dist#

        LineCollisionY=y#-l\ny*dist#

                

        Return Abs(dist#)

        

End Function



;Returns true if a point collides with a line within range r

Function LineCollide(l.cline,x#,y#,r#)

        

        dx1#=x-(l\x1-l\ux*r)

        dy1#=y-(l\y1-l\uy*r)

        

        d#=Sqr(dx1*dx1+dy1*dy1)

        

        dx1=dx1/d

        dy1=dy1/d

        

        dx2#=x-(l\x2+l\ux*r)

        dy2#=y-(l\y2+l\uy*r)

        

        d#=Sqr(dx2*dx2+dy2*dy2)

        

        dx2=dx2/d

        dy2=dy2/d

        

        dot1#=dx1*l\ux+dy1*l\uy

        dot2#=dx2*l\ux+dy2*l\uy

        

        Return ((dot1#>=0 And dot2#<=0) Or (dot1#<=0 And dot2#>=0)) And (LineDistance(l,x,y)<=r)

        

End Function



Type circle



        Field x#,y#,vx#,vy#

        

        Field vel#



        Field r#



End Type



Function CircleNew.circle(x#,y#,r#=50,vx#=0,vy#=0)

        

        c.circle=New circle

        c\x=x

        c\y=y

        c\r=r

        c\vx=vx

        c\vy=vy

        

        CirclePlace(c)

        

        Return c

End Function



Function CirclePlace(c.circle,w#=800,h#=600)

        

        num=0

        While CirclePlaceTest(c,c\x,c\y)=False And num<1000

        

                c\x=Rnd(w)

                c\y=Rnd(h)

        

                num=num+1

        

        Wend

        

End Function



;Returns true if a circle can be placed, it doesn?t collide with any other circles or lines

Function CirclePlaceTest(c.circle,x#,y#)



        For cc.circle=Each circle

                If cc<>c

                        dx#=cc\x-c\x

                        dy#=cc\y-c\y

                        d#=Sqr(dx*dx+dy*dy)

                        If d<(c\r+cc\r)

                

                                Return False

                                

                        EndIf

                EndIf

        Next



        For l.cline=Each cline



                If LineCollide(l,c\x,c\y,c\r)

                                

                        Return False

                                        

                EndIf



        Next



Return True



End Function



;draw circles

Function CircleDraw()



Color 0,0,255

For c.circle=Each circle

        

        rh#=c\r*2



        Oval c\x-c\r,c\y-c\r,rh,rh



Next





End Function



Function CircleUpdate()



For c.circle=Each circle



        ;Calculate total velocity

        c\vel#=Sqr(c\vx*c\vx+c\vy*c\vy)

        

        ;collision against other circles

        For cc.circle=Each circle

                ;do not test against itself

                If cc<>c

                        ;vector from one circle to another

                        dx#=cc\x-c\x

                        dy#=cc\y-c\y

                        d#=Sqr(dx*dx+dy*dy)

                        ;check of distance is smaller than the two circle?s radii together

                        If d<(c\r+cc\r)

                

                                ;make the vector a unit vector (length=1), multiply it with the circle?s

                                ;total velocity, to get the new motion vector

                                c\vx=(-dx#/d) * c\vel

                                c\vy=(-dy#/d) * c\vel

                        

                        EndIf

                EndIf

        Next

        

        ;collision agains lines

        For l.cline=Each cline



                ;Check if circle collides with a line

                If LineCollide(l,c\x,c\y,c\r)

                

                        ;create a mark, where the circle has colliede with the line

                        PoofNew(LineCollisionX,LineCollisionY)

                                

                        ;Get the dot product between the circles motion vector and the line?s normal vector

                        dot#=c\vx*l\nx+c\vy*l\ny        

                        

                        ;Calculate the circle?s new motion vector

                        c\vx=c\vx-2.0*l\nx*dot

                        c\vy=c\vy-2.0*l\ny*dot

                                        

                EndIf



        Next

        

        ;add velocity to position

        c\x=c\x+c\vx

        c\y=c\y+c\vy

        

        ;Wrap to screen boundaries

        If c\x>GraphicsWidth()

                c\x=0

        EndIf

        

        If c\y>GraphicsHeight()

                c\y=0

        EndIf



        If c\x<0

                c\x=GraphicsWidth()

        EndIf        

        

        If c\y<0

                c\y=GraphicsHeight()

        EndIf

Next



End Function



Type poof



        Field x,y

        

        Field age#

        

        Field maxage

        

End Type



Function PoofNew.poof(x,y,age#=20)

        

        p.poof=New poof

        

        p\x=x

        p\y=y

        p\maxage=age

        

        Return p

End Function



Function PoofUpdate()



For p.poof=Each poof

        p\age=p\age+1



        If p\age>=p\maxage

        

                Delete p

                

        EndIf



Next



End Function



Function PoofDraw()



For p.poof=Each poof

                        

        pah=p\age*0.5

                

        Oval p\x-pah,p\y-pah,p\age,p\age,0

                

Next



End Function



Graphics 800,600,0,2



linex1#= 7

liney1# = 20

linex2#= 371

liney2# = 350



circlex#= 300

circley# = 200

circler# = 70



Line linex1, liney1, linex2, liney2

Oval circlex-circler, circley-circler, circler*2, circler*2



If LineToCircle( linex1, liney1, linex2, liney2, circlex, circley, circler) Then

        Text 10,100, "Collided."

Else

        Text 10,100, "Not collided."

End If 







WaitKey







Function LineToCircle( lx1#, ly1#, lx2#, ly2#, cx#, cy#, r#)



dx# = lx2 - lx1

dy# = ly2 - ly1

ld# = Sqr((dx*dx) + (dy*dy))

lux# = dx / ld

luy# = dy / ld

lnx# = luy

lny# = -lux

dx1# = cx - (lx1 - lux*r)

dy1# = cy - (ly1 - luy*r)

d# = Sqr((dx1*dx1) + (dy1*dy1))

dx1 = dx1 / d

dy1 = dy1/ d

dx2# = cx - (lx2 + lux * r)

dy2# = cy - (ly2 + luy*r)

d = Sqr((dx2*dx2) + (dy2*dy2))

dx2 = dx2  / d

dy2 = dy2 / d

dot1# = (dx1 * lux) + (dy1 * luy)

dot2# = (dx2 * lux) + (dy2 * luy)

px#=lx1-cx

py#=ly1-cy

distsq# = Abs((dx * py - px * dy)  / ld )



;You can get point of collision using these two variables (make them global)

;LineColX# = cx - lnx * sqr(distsq) 

;LineColY# = cy - lny * sqr(distsq)





Return (( dot1>=0 And dot2<=0) Or (dot1<=0 And dot2>=0)) And (distsq <= r)





End Function