<p>Boids handlar om att simulera flockar genom självständiga individer. Styrningen utgår från tre grundregler, undvika kollision, centrera flocken samt matcha hastighet. För att framhäva vissa beteenden kan reglerna viktas. Dessa vikter kan sättas manuellt, men de kan också optimeras, exempelvis med genetiska algoritmer. Detta examensarbete utgår från Chen, Kobayashi, Huang och Nakao (2006) arbete om optimering av boids med hjälp av en genetisk algoritm. Beteende hos flockar med manuellt satta vikter och optimerade med en genetisk algoritm jämförs. Jämförelsen sker genom mätningar enligt kriterier som reflekterar hur realistiskt flocken beter sig. Försöken påvisade två olika beteenden, ett där flocken centreras och ett där kollision och leta mat får prioritering.</p>

Context. Simulation of nature is something that is used to immerse the player into the world of games. By adding details in the world such as birds circling in the sky or small fishes swimming in a flock, developers can improve the gaming experience for the user. More precise simulations are something that should be aspired for. This thesis will explore the boid flocking algorithm and evaluate what settings users perceive as realistic behavior for simulating schools of fish. Objectives. This thesis proposes that there should be a set of variables that reflect a more realistic behavior and through gathering data from volunteers and mapping their answers, conclude if that statement is true. Methods. A boid simulation will be run in a number of different scenarios, each differing in variables that are vCohesion, vSeparationand vAmount that make changes to the overall behavior. This behavior is then recorded and compared next to each other in a perceptual experiment with the objective of finding out the preferred settings interms of realism. Results. The experiment showed that the preferred value of vSeperation was around 50 to 60 world units. The value of vCohesion and vAmount was random to what was perceived, so their impact on realism was not significant enough. Conclusions. After running the experiment it was apparent that there was a preferred value on some of the variables that were examined. The larger impact on realism was in the distance each boid wanted to keep from its neighbor, the vision range of each boid defined what was considered a neighborhood. The range on this variable was not of much importance and did not impact what the user perceived as realistic.

Boids handlar om att simulera flockar genom självständiga individer. Styrningen utgår från tre grundregler, undvika kollision, centrera flocken samt matcha hastighet. För att framhäva vissa beteenden kan reglerna viktas. Dessa vikter kan sättas manuellt, men de kan också optimeras, exempelvis med genetiska algoritmer. Detta examensarbete utgår från Chen, Kobayashi, Huang och Nakao (2006) arbete om optimering av boids med hjälp av en genetisk algoritm. Beteende hos flockar med manuellt satta vikter och optimerade med en genetisk algoritm jämförs. Jämförelsen sker genom mätningar enligt kriterier som reflekterar hur realistiskt flocken beter sig. Försöken påvisade två olika beteenden, ett där flocken centreras och ett där kollision och leta mat får prioritering.

Målet med denna studie var att jämföra felfrekvensen i gruppsammanhållning mellan två system med avseende på gruppstorlek. I det ena systemet skedde relationsförändringar på en individualistisk basis, där en agents slumpade åsikt avgjorde utfallet av interaktioner med andra agenter med åsikter. Det andra systemet var en utsträckning av den första som även tillämpade en kollektivistisk relationsförändring, vilket lägger till en relationsförändring baserat på vad alla andra agenter har för relationsvärden. Experiment utfördes där felfrekvensen mättes genom att utvärdera hur många testfall som hade en misslyckad gruppsammanhållning efter testets slut. Denna utvärdering visade att det individualistiska systemet hade en ökande felfrekvens i samband med ökande gruppstorlek, och det kollektivistiska systemet verkar ha en stadig felfrekvens oavsett gruppstorlek. Den största gruppen som utvärderats i detta arbete bestod av 15 agenter, vilket visade sig otillräckligt för att avgöra exakt hur den kollektivistiska felfrekvensen förändras med avseende på gruppstorlek. Att utvärdera större grupper har lämnats till framtida arbete. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p><p>There are other digital material (eg film, image or audio files) or models/artifacts that belongs to the thesis and need to be archived.</p>

With the multi-layered flocking system it is possible to simulate flocks that contain different types of agents that can be of various different sizes (variations in bounding radius and height). In the original implementation, the multi-layered flocking system uses a metric distance to find the nearest-neighbours of agents. However, results from real life field studies suggest that animals interact with each other in a flock using a topological distance. The goal of this thesis is therefore to implement a version of the multi-layered flocking system that uses a topological distance for interaction between agents. This is done by adapting two methods that are used to find the k-nearest neighbours (kNN), namely the original spatial partitioning method (OSP method) and the enhanced spatial partitioning method (ESP method), to work with the multi-layered flocking system. The aim is to compare the performance of these methods in terms of query time for four different flocking scenarios (standard, obstacle, follow and steer away). The implementation contains two types of agents of two different sizes. In the standard scenario all agents move together as a flock. The obstacle scenario is similar to the standard scenario with the addition that the simulation space contains stationary obstacles. In the follow scenario the smaller sized agents follow the bigger sized agents, and in the steer away scenario the smaller sized agents steer away from the bigger sized agents. An evaluation of how different numbers of kNN affect the collective motion (polarization, extension and frequency of collisions) of the flock in the four different scenarios is also done. The evaluation was performed by implementing the multi-layered flocking system in the Unity game engine, and running simulations with flocks of different sizes (125-3125 agents) and using different numbers of interacting kNN (k=5,10,15,20) for each of the scenarios. The results show that the ESP method on average is at least twice as fast compared to the OSP method in all four flocking scenarios, and the improvement in performance in query time did not differ much between the scenarios. Moreover, a value of k=10 was shown to be a good compromise between having fast kNN query times for the ESP method, but still having flocks of agents moving in a collective manner. / Med ett flerskiktigt flockningssystem är det möjligt att simulera flockar som innehåller olika typer av agenter som kan vara av olika storlekar (variation i begränsningsradie och längd). I den ursprungliga implementeringen av det flerskiktigt flockningssystem används ett metriskt avstånd för att hitta de närmaste grannarna till agenterna. Resultat från fältstudier tyder dock på att i verkligheten interagerar djur i en flock med varandra genom ett topologiskt avstånd. Målet med denna avhandling är därför att implementera en version av det flerskiktigt flockningssystem som använder ett topologiskt avstånd för att hitta de närmaste grannarna till agenterna. Detta görs genom att anpassa två metoder som kan användas för att hitta en agents k-närmaste grannar till det flerskiktigt flockningssystem. Dessa två metoder kallas den ursprungliga spatiala partitioneringsmetoden (OSP metoden) och den förbättrade spatiala partitioneringsmetoden (ESP metoden). Syftet är att jämföra prestandan mellan dessa två metoder, vilket mäts i tid som det tar att hitta de k-närmaste grannarna för varje metod. Jämförelser genomförs för fyra olika typer av scenarion (standard, hinder, följ och styr ifrån). I standard scenariot rör sig alla agenter tillsammans som en flock. Hinder scenariot liknar standard scenariot med tillägget att simuleringsmiljön består av ett antal stationära hinder. I följ scenariot så följer de mindre agenterna de större agenterna, och i styr ifrån scenariot så försöker de mindre agenterna fly från de större agenterna. Vidare görs en utvärdering av hur olika antal k-närmaste grannar påverkar den totala flockens samlade rörelse (polarisering, förlängning och frekvens av kollisioner) för de olika scenarierna. Utvärderingen görs genom att implementera det flerskiktiga flockningssystemet med de ovan nämnda k-närmaste grannar metoderna i spelmotorn Unity. Ett flertal simuleringar genomförs sedan för de fyra scenarierna och dessa består av olika flockstorlekar (125-3125 agenter) och använder olika värden på k (k=5,10,15,20). Resultaten visar att ESP metoden i genomsnitt är dubbelt så snabb jämfört med OSP metoden. Dessutom visades ett värde på k=10 vara en bra kompromiss mellan att snabbt hitta de k-närmaste grannarna när ESP metoden används, men också ha flockar av agenter som rör sig kollektivt.

Detta arbete använder genetiska algoritmer för att få fram ANN hos boids utifrån två uppsättningar regler och jämför de resulterande beteendena med varandra. Boids är simulerade fåglar i en fågelflock som var för sig styrs med enkla regler men som tillsammans bildar ett flockbeteende. Genetiska algoritmer liknar naturens evolution. En population vars egenskaper kodas på ett genom blir bättre på de egenskaperna genom att de bästa individerna väljs ut och får utvecklas mer medans de sämre rensas bort. ANN står för artificiella neurala närvek och ska likna biologiska neurala nätverk och ska med andra ord fungera som en hjärna. Boids följer normalt tre regler. Centrering, hastighetsmatchning och undviker kollisioner. Detta arbete undersöker om boids beter sig mer naturligt om de även måste leta mat och undvika fiender. Det undersöker också en metod för att objektivt kunna mäta naturlighet.

I detta examensarbete tittas det närmare på taktiska beslut för större grupper av autonoma agenter. Arbetet ska försöka besvara följande frågeställning: Hur effektivt kan svärm-AI användas för att utföra taktiska beslut när det appliceras till ett spel med grupper av fiender? För att kunna besvara frågeställningen skapades en applikation där fyra kombinationer av styrbeteenden och beräkningsmodeller inom tekniken ”boids” användes. Inom två av kombinationerna användes traditionella styrbeteenden inom boids, och inom de andra introducerades ett styrbeteende för att flankera spelaren för att ge bättre resultat. Resultatet av arbetet visar att kombinationerna med de taktiska besluten fick överlägset bättre resultat och gav därmed goda förhoppningar för att besvara frågeställningen, men för att kunna ge ett definitivt svar på hur effektivt det är visade det sig att en större bredd av experiment hade behövts användas. Taktisk svärm-AI kan användas utanför datorspel, till exempel inom robotik och att simulera större militära slag.

----- / As processor performance capabilities can only be increased through the useof a multicore architecture, software needs to be developed to utilize the parallelismoffered by the additional cores. Especially game developers need toseize this opportunity to save cycles and decrease the general rendering time.One of the existing advances towards this potential has been the creation ofmultithreaded game engines that take advantage of the additional processingunits. In such engines, different branches of the game loop are parallelized.However, the specifics of the parallel design patterns used are not outlined.Neither are any ideas of how to combine these patterns proposed. Thesemissing factors are addressed in this article, to provide a guideline for whento use which one of two parallel design patterns; fork-join and pipeline parallelism.Through a collection of data and a comparison using the metricsspeedup and efficiency, conclusions were derived that shed light on the waysin which a typical part of a game loop most efficiently can be organized forparallel execution through the use of different parallel design patterns. Thepipeline and fork-join patterns were applied respectively in a variety of testcases for two branches of a game loop: a BOIDS system and an animationsystem.

No description available.

Made available in DSpace on 2016-03-15T19:37:44Z (GMT). No. of bitstreams: 1 Diego Gadens dos Santos.pdf: 2663525 bytes, checksum: 46be86494cd52896593a08e979b2a0ce (MD5) Previous issue date: 2012-09-14 / Fundo Mackenzie de Pesquisa / Current technologies have made it possible to generate and store data in high volumes. To process and collect information in large databases is not always as easy as creating them. Therefore, this gap has stimulated the search for efficient techniques capable of extracting useful and non-trivial knowledge, which are intrinsic to these large data sets. The goal of this work is to propose a bioinspired algorithm, based on the Boids artificial life model, which will be used to group data in dynamic environments, i.e. in databases updated over time. The Bo-ids algorithm was originally created to illustrate the simulation of the coordinated movement observed in a flock of birds and other animals. Thus, to use this algorithm for data clustering, some modifications must be applied. These changes will be implemented in the classical rules of cohesion, separation and alignment of the Boids model in order to consider the distance (similarity/dissimilarity) among objects. Thus, it creates objects that stand and move around the space, representing the natural groups within the data, and it is expected that similar ob-jects tend to form dynamic clusters (groups) of Boids in the environment, while dissimilar objects tend to keep a larger distance between them. The results presented attest the robust-ness of the algorithm for clustering time-varying data under the light of different evaluation measures and in various databases from the literature. / A capacidade de geração e armazenamento de dados proporcionada pelas tecnologias atuais levou ao surgimento de bases de dados com uma grande variedade de tipos e tamanhos. Extra-ir conhecimentos não triviais e úteis a partir de grandes bases de dados, entretanto, é uma tare-fa muito mais difícil do que a criação das mesmas. Esta lacuna tem estimulado a busca por técnicas eficientes de extração de conhecimentos intrínsecos a estes grandes conjuntos de da-dos, capazes de permitir tomadas estratégicas de decisão. Dentre as muitas tarefas da extração de conhecimentos a partir de dados, tem-se o agrupamento, que consiste na segmentação da base em grupos cujos objetos são mais parecidos entre si do que a objetos pertencentes a ou-tros grupos. Apesar de a área ser bastante ativa, pouco tem sido feito no sentido de desenvol-ver e investigar algoritmos de agrupamento para dados variantes no tempo, por exemplo, tran-sações financeiras, dados climáticos, informações e mensagens postadas em redes sociais e muitos outros. Tendo em vista a relevância prática desse tipo de análise e o crescente interesse pelos algoritmos inspirados na biologia, este trabalho tem como objetivo propor um algoritmo bioinspirado, baseado no modelo de vida artificial de Boids, para realizar o agrupamento de dados variantes no tempo. O algoritmo de Boids foi inicialmente criado para demonstrar ape-nas a simulação da movimentação coordenada observada em uma revoada de pássaros. A fim de utilizar este algoritmo para a tarefa de agrupamento de dados, algumas modificações tive-ram de ser propostas nas regras clássicas de coesão, separação e alinhamento dos Boids. Desta forma, foram criados objetos que se posicionam e se movimentam no espaço, de maneira a representar os grupos naturais existentes nos dados. A característica dinâmica intrínseca dos Boids tornou o algoritmo proposto, denominado dcBoids (dynamic clustering Boids), um can-didato natural para a resolução de problemas de agrupamento de dados variantes no tempo. Os resultados obtidos atestaram a robustez do método em seu contexto de aplicação, sob a pers-pectiva de diferentes medidas de avaliação de desempenho e quando aplicado a várias bases de dados da literatura com dinâmicas inseridas artificialmente.