Simulatorul de Trafic

Cuprins

Introducere

Simulatorul de trafic

Caracteristicile principale ale simultoarelor de trafic

Grafica pe calculator

Mediul Unity3D

Tema și obiectivele proiectului

Tema

Obiectivele principale

Proiectarea software

Algoritmi și tehnici de programare

Structuri de date

Proiectarea software (diagrame uml use case )

Sinteza algoritmilor de control

Noțiuni preliminare

Algoritmi de control

Implementarea

Tehnici de optimizare utilizate

Optimizarea graficii

Optimizarea algoritmilor software

Avantajele optimizării

Posibilități de dezvoltare ulterioară

Concluzii

Bibliografie

1. Introducere

Simulatorul de trafic

Simulatorul de trafic ofera o abordare eficienta din punct de vedere al costului, obiectivă și flexibilă. Odata cu dezvoltarea tehnologiei calculatoarelor, modelele numarice au devenit o unealtă importanta în proiectarea și testarea sistemelor de control al traficului autovehiculelor. Scopul principal al acestor modele este realizarea unor Sisteme Inteligente de Transport. Acestea au rolul de a aduna date reale din trafic și de a lua decizii de control printr-o estimare cat mai corectă a fluxului de trafic.

Simularea pe calculator a modelelor de trafic joaca un rol tot mai important în analiza sistemelor din zolele urbane și a autostrazilor, datorata capacitații de a modela condiții diferite de trafic, strategii de control și comportamentul conducatorilor auto. În aceste scopuri s-au dezvoltat numeroase sisteme complexe, capabile sa simuleze cele mai variate caracteristici. Simulatoarele se pot clasifica în mai multe categorii, cum ar fi: statice sau dinamice, deterministe sau stohastice, microscopice sau macroscopice. Fiecare tip de simulator are logica, algoritmii și limitarile proprii, și este aplicabil unei anumite componente din sistemul de transport.

Multe experimente și aplicații ale modelelor de trafic s-au realizat pentru a lua cele mai potrivite decizii în sistemele de trafic real. Prin utilizarea tehnicilor de simulare, specialistii pot sa analizeze formarea și disparitia blocajelor și aglomerarilor pe rutele de transport, sa evalueze actiunile sistemelor de control și sa compare diferite configuratii posibile.

Majoritatea simulatoarelor folosite în mod curent sunt în continua dezvoltare și imbunatatire. Lipsa unui model general de verificare și calibrare, simplificarile implicite facute pentru modelul logic și numarul mare de valori de intrare și timpi mari de executie duc la rezultate ale simulării care sunt fie limitate, eronate sau imposibil de realizat fizic. Problemele de simulare trebuie luate totdeauna în calcul inainte de aplicarea solutiilor oferite intr-o componenta de trafic reala.

Figura 1.1 Simulator de trafic

Simulatoarele de trafic sunt analizeaza modelele reale dintr-o perspectiva microscopica, macroscopica sau mesoscopica. Rezultatele simularilor se pot aplica atat în sistemele de planificare și control a transporturilor, cat și cele de proiectare. În sistemele de planificare, modelele calculeaza efectele algoritmilor de dezvoltare urbana pe regiuni în performanta infrastructurii de trafic. Organizatiile de planificare regionala folosesc aceste modele de simularea ca sa calculeze cazurile posibile din zonele critice, cum ar fi blocaje sau zone care incetinesc traficul. Sunt investigate astfel tipul de cai de acces, temporizarea semafoarelor, strazile cu sens unic, intersectiile și controlul traficului pe autostrazi pentru imbunatatirea sistemelor locale de trafic. Unele simulatoare sunt utilizate pentru proiectarea fie a sistemelor, fie a elementelor de cotrol al traficului; unele au capacitatea de modelare a ambelor componente.

Transportul pasagerilor și bunurilor este domeniul cel mai folosit în simulatoare de trafic. Simularea poate fi realizata în sisteme simple sau mai complexe, cu rețele de trafic complicate. Se poate analiza astfel drumurile optime, și se pot evita intarzierile, congestionarea traficului, poluarea excesiva. Modele de trafic pot include toate tipurile de transport rutier, incluzand masini mici, autobuze, camioane și motocilete. În simulatoare insa se folosesc de obicei vehicule similare, care functioneaza aproximativ dupa aceleasi principii și urmeaza aceleasi reguli de conducere; în simularile de nivel microscopic performanta retelei de trafic și comportamentul soferilor este luat în calcul ca sa ofere rezultate mai exacte.

Caracteristicile principale ale simulatoarelor de trafic

Simulatoarele de trafic iau în considerare fluxul de autovehicule, viteza și densitatea și le integreaza cu diferite tehnici de analiza. Ele se clasifica astfel, în principal, prin modul de integrare, prin algoritmii folositi și modelele generate pentru a reprezenta comportamentul participantilor la trafic.

Cele mai utilizate abordari matemetice pentru simulatoarele de trafic sunt modelul macroscopic și cel microscopic. Modelul macrosocpic studiaza proprietatile rezultate din interactiunea unor grupuri de automobile și ignora complet detaliile individuale ale participantilor la trafic. Modelul de flux dinamic considera miscarea masinilor la fel ca cea a unui fluid compresibil. În acest caz, variabilele principale, debitul, densitatea și viteza sunt functii de spatiu și timp. Astfel, scopul este sa construim ecuatii diferentiale pentru aceste variabile și sa le rezolvam.

Odata cu utilizarea cat mai frecventa a senzorilor de detectie și supraveghere a rutelor de trafic, avem cantitati tot mai mari de date la dispozitie. Acesta ne dau posibilitatea sa construim modele bazate pe date pentru predictia fluxului de trafic.

O alta abordare a modelelor de simularea este cel microscopic. Acesta studiaza miscarile individuale ale automobilelor și iau în calcul toate caracteristicile și comportarile conducatorilor auto. În ultima perioada de timp, modelul microscopic a fost folosit tot mai mult intr-o serie de aplicații de simulare cu aplicații în proiectarea rețelelor, rezolvarea problemelor de trafic, realizarea Sistemelor Înteligente de Transport și a altor strategii de management al traficului. Un avantaj importnat al simulării este acela ca ofera informatii din sistem de la fiecare componenta majora a acestuia și de la fiecare nivel ierarhic. Datele rezultate se pot folosi la acordarea senzorilor și reduc drastic costurile testarii în mediul real de trafic.

Pe langa simularea modelelor individuale, este mai important adesea simularea rețelelor multi-modale, deoarece rezultatele devin mai complete și mai exacte. Simularea retelor intermodale poate sa reprezinte efectele elementelor de control asupra sistemelor dintr-o perspectiva mai larga. Un exemplu de simulator intermodal este Commuter realizat de compania Azalient, care introduce atat moduri dinamice și cu alegere pentru agentii din simulare. Acest tip de modelare este denumit nanosimulare, și este considerat cu rezultate mai detaliate decat microsimularile traditionale. Simularea traficului poate fi integrata cu mediul urban simulat, care include o zona mare de oras, cu rețele complexe de trafic, pentru o mai buna intelegere a folosirii elementelor de conrol și comnada acestora.

Programele de simulare devin tot mai performante din mai multe puncte de vedere. Datorita noilor imbunatatiri din matematica, automatica și stiinta calculatoarelor, simulatoarele sunt tot mai rapide, mai puternice și mai realiste.

Un simulator este, prin urmare, o reprezentare matematica a unui sistem dinamic din care se pot trage concluzii asupra proprietatilor sistemului real. Timpul este o variabila de baza independenta a unui model de simulator. În simulatoarele implementate pe calculator, starea sistemului este recalculata la momente discrete de timp; cu cat momentele de timp sunt mai apropiate, cu atat rezultatele sunt mai corecte și apropiate de realitate, adica de sistemul original. Mediul de simulare poate aplica o scanare bazata pe timp, în care modelul este recalculat la intervale regulate sau o strategie bazata pe evenimente discrete în care sistemul este recalculat în acele momente în care starea lui se modifica. Recalcularea bazata pe evenimente necesita mai putine resurse și incarca procesorul mai putin deoarece calculele nu re realizeaza la fel de des ca și la sistemele bazate pe timp, cu toate ca rezultatele sunt similare. Simularea bazata pe evenimente necesita în schimb calculul modificarilor în starea urmatoare, dupa fiecare update. Acest lucru devine complex pentru sistemele care isi schimba fecvent starea și valorile parametrilor, asa ca aceasta strategie este utilizata pentru acele modele cu dimensiune mai redusa și pentru cele care isi pastreaza o durata lunga starea. Sistemele cu scanare bazata pe timp se utilizeaza în cazul în care aceste contin un numar mare de entitati (automobile) care isi schimba fecvent parametrii.

Figura 1.2 Relatia dintre modelele de simulare

Sistemele de simulare pot sa fie deterministe sau stohastice. Modele deterministe nu includ parametrii aleatori și sunt aplicabile sistemelor ale caror parametrii variaza dupa legi bine definite. Simulatoarele stohastice folosesc o distributie statistica pentru unii dinte parametrii pentru a realiza o variabilitate a sistemului real. Rezultatul unei simulari al unui model stohastic va diferi în functie de variatia aleatoare a parametrilor din sistem.

Simulatoarele de trafic au fost proiectate sa mimeze evolutia în timp a operatiunilor de trafic intr-o retea rutiera. La inceputul utilizarii lor, ele functionau pe un model bazat pe evenimente, din cauza limitarii puterii de calcul a calculatoarelor. Rezultatele erau astfel destul de limitate. Din cauza numarului mare de evenimente ce apar intr-un sistem de trafic în mai multe locatii din sistem, simulatoarele aveau foarte putine proprietati variabile ale traficului, prin urmare o flexibilitate redusa. Din cauza aplicabilitatii reduse, modele bazate pe evenimente au evoluat odata cu dezvoltarea stiintei calculatoarelor și puterii lor de procesare. La ora actuala se utilizeaza majoritar simulatoare bazate pe timp, fie modele deterministe, fie stohastice. Din moment de traficul de autovehicule include o mare varietate a parametrilor, modelele deterministe pot fi vazute ca și o reprezentare a unei stari medii a sistemului. Pentru modele stohastice media sistemului se poate realiza numai printr-un numar de simulari, cu diferite valori în limitele stabilite a parametrilor.

Un simulator de trafic consta din reprezentarea retelei impreuna cu elementele simulate. Reteaua de drumuri include atat infrastructura propriu-zisa (caile de acces) cat și sistemele de control al traficului. Simulatoarele de trafic se clasifica în mode curent în functie de nivelul de detaliu al modelarii fluxului de trafic. Simularile macroscopice folosesc parametrii cum ar fi viteza medie, fluxul și densitatea pentru a definii fluxul de trafic sau, cu alte cuvinte, condițiile de trafic intr-un model macroscopic sunt definite de relatiile fundamentale intre flux, viteza și densitate. Simularile macroscopice sunt capabile sa modeleze rețele mari de trafic din cauza modelului abstract prin care lucreaza. Cele mai folosite aplicații ale simulării macroscopice sunt, din acest motiv, analiza operatiunilor și optimizarilor traficului din retelele de trafic din orasele mari sau pe autostrazi.

Exemple de simulatoare cu model macroscopic sunt cele cu transmisie în celule (Daganzo, 1994) și Metanet (1990). Printr-un model macroscopic este dificil sa exemplifici consecintele elementelor dintr-un sistem de trafic care au efect asupra automobilelor individuale sau particulare, sau proprietatilor care depind de comportamentul acestor automobile. Spre exemplu, studiul intersectiilor din autostrazi, caile de pasaj din zonele urbane, și aplicatiile sistemelor inteligente de transport (ITS – Întelligent Tabile sa modeleze rețele mari de trafic din cauza modelului abstract prin care lucreaza. Cele mai folosite aplicații ale simulării macroscopice sunt, din acest motiv, analiza operatiunilor și optimizarilor traficului din retelele de trafic din orasele mari sau pe autostrazi.

Exemple de simulatoare cu model macroscopic sunt cele cu transmisie în celule (Daganzo, 1994) și Metanet (1990). Printr-un model macroscopic este dificil sa exemplifici consecintele elementelor dintr-un sistem de trafic care au efect asupra automobilelor individuale sau particulare, sau proprietatilor care depind de comportamentul acestor automobile. Spre exemplu, studiul intersectiilor din autostrazi, caile de pasaj din zonele urbane, și aplicatiile sistemelor inteligente de transport (ITS – Întelligent Transportation System) sunt dificil de modelat printr-o reprezentare macroscopica.

Figura 1.3 Simulator de trafic microscopic

Sistemele inteligente de transport pot fi descrise ca totalitatea elementelor de telecomunicatie, sisteme de calcul și sisteme de control automat ce interactioneaza cu automobilele în sistemul de trafic și au capacitarea de a utiliza eficient resursele puse la dispozitie. Termenul de sisteme inteligente de transport se utilizeaza pentru o multime de aplicații ale sistemelor de management de trafic, sisteme de informare a traficului și sistemele de ajutare a conducatorilor auto. Multe dintre aceste sisteme s-au dezvoltat pentru a ajuta automobile individuale în fluxul de trafic. Pentru studiul acestor sisteme, simulatoarele cu modelare microscopica realizeaza o descriere completa a fluxului de trafic.

Simularile cu model microscopic iau în considerare automobile individuale în modelarea traficului. În timpul rularii simulării, automobilele isi modifica pozitia prin reteaua de drumuri, intre punctul de origine și cel de destinatie. Înteractiunile dintre automobile și celelalte sau intre automobile și infrastructura cailor de acces sunt modelate în timpul acestui proces prin ecuatii menite sa mimeze comportamentul real al conducatorilor. Din cauza ca traficul este simulat cu atata precizie, diferite medii de drum vor avea cerinte diferite asupra modelelor de simulare. Cerintele de modelare pentru un simulator al fluxului de trafic pentru un drum rural sunt forate diferite, spre exemplu, de cerintele unui simulator folosit în traficul urban sau pe autostrazi. Aceasta este din cauza diferentelor fundamentale în interactiunea dintre automobile și infrastructura retelei de trafic. Spre exemplu, adaptarea vitezei la geometria drumului are un rol mai important pe strazile din zonele rurale, decat pe cele din zonele urbane. Modele care reprezinta fluxul de trafic de pe strazile rurale trebiue sa ia în considerare interactiunea dintre autoturisme și infrastructura drumurilor în detaliu, mai mult decat cele din zonele urbane. Înteractiunile intre masini sunt de asemenea importante, mai ales în situatiile de depasire sau posibilități de coliziune.

Figura 1.4 Simulator mesoscopic CONTRAM

Descrierea în detaliu a traficului intr-un model de micro-simulare duce la durate mari de procesare pentru relele de dimensiuni mari. Prin urmare, modelele microscopice sunt folosite pentru zone mai reduse ca dimensiuni. Cele mai multe aplicații ale acestor modele sunt studiile de capacitate și a niveleor de disponibilitate a zonelor din retelele de trafic urban sau pe autostrazi. Ele mai sunt folosite tot mai mult și pentru determinarea sigurantei și a emisiilor poluante.

O a treia clasa de modele de simulare este cea mesoscopica. Nivelul de detaliu utilizat de aceasta clasa de simulatoare este intre cea macroscopica și microscopica. Scopul lor este simularea rețelelor de trafic de dimensiuni medii și cu un nivel de detaliu destul de ridicat. Exemple de simulatoare cu model mesoscopic sunt CONTRAM și Mezzo.

Grafica pe calculator

Grafica pe calculator consta din reprezentari ale modelelor reale, afisate sub forma unor imagini bidimensionale cu ajutorul calculatorului și componentelor hardware și software specializate. Dezvoltarea graficii pe calculator reprezinta un pas important dezvoltarea simulatoarelor și a modalitatilor de vizualizare și interpretare a datelor procesate. Ea are de asemenea și un impact important și în alte domenii, cum ar fi industria jocurilor, animatiilor și filmelor.

Grafica pe calculator cuprinde nu numai manipularea și reprezentarea imaginilor de catre unitatile de calcul, dar și numeroase tehnologii software și hardware, fara de care acestea nu ar fi posibile. Imaginile generate pe calculator se pot clasifica în doua mari categorii: imagini bidimensionale ( 2D ) și imagini tridimensionale ( 3D ). Odata cu dezvoltarea stiintei calculatoarelor, imaginile și animatiile tridimensionale au devenit tot mai raspandite și mai folosite, dar și cele bidimensionale isi pastreaza locul.

Modelarea 3D reprezinta generarea unui model 3D prin intermediul programelor pe calculator. O „scena” este un fisier scris intr-un limbaj specific care contine geometria obiectelor, punctele de vizualizare, texturile, luminile, umbrele și alte efecte grafice. Programul de modelare utilizeaza un motor grafic, care realizeaza conexiunea intre el și driver-ul placii grafice. Desii detaliile tehnice a modelarii variaza de la program la program, principala problema este transpunerea unei imagini 2D dintr-un model 3D definit intr-un fisier de pe hard-disk. Aceasta transpunere se realizeaza cu ajutorul GPU (graphics processing unit).

Figura 1.5 Model 3D realizat cu Autodesk 3ds Max

Mediul Unity3D

Unity3D este un motor grafic 3D care permite realizarea de aplicații interactive pe o larga varietate de dispozitive electronice și sisteme de operare. Mediul utilizeaza pentru randarea grafica unele dintre cele mai folosite motoare 3D, cum ar fi: Direct3D (Windows, Xbox 360), OpenGL (Mac, Windows, Linux), OpenGL ES (Android, iOS). El permite astfel utilizarea a numeroase efecte grafice de ultima generatie: umbre generate dinamic, reflexii, materiale pentru suprafete. În el se pot importa foarte usor modele grafice 3D realizate în alte programe de design grafic.

În privinta limbajelor de programare, Unity3D se bazeaza pe Mono, o inplementare open-source a framework-ului .NET. Pentru realizarea algoritmilor, codul poate fi scris în UnityScript (limbaj asemanator cu JavaScript), C# sau Boo (limbaj asemanator cu Pyhton). Pentru aceasta lucrare, am ales limbajul C#, fiin un limbaj de nivel inalt, foarte des utilizat și care nu are probleme de compatibilitate.

Figura 1.6 Înterfata de utilizare Unity3D

Un mare avantaj al mediului Unity este motorul de simulare fizic inclus PhysX, dezvoltat de firma Nvidia. Asta face din el un perfect mediu de dezvoltare a aplicatiilor de simulare, fiind posibila și portarea lor pe dispozitivele mobile.

2. Tema și obiectivele proiectului

Tema proiectului

Aceasta lucrare prezinta un model simplificat de simulator de trafic realizat în mediul de programare Unity3D, care prezinta grafic o portiune dintr-o retea de trafic urban. Principalele elemente prezente în simulare sunt autovehiculele, reteaua de drumuri și semafoarele. Momentan, simularea nu ia în considerare existenta pietonilor, prin urmare nu este în totalitare realista. Cu toate acestea, ea ramane un important model pentru studiul traficului urban și o unealtă importanta în luarea unor decizii de optimizare a traficului.

Toate elementele grafice prezente în lucrare reprezinta la baza modele 3D realizate în mediul de dezvoltare Autodesk 3ds Max. Ele au rolul de a modela grafic comportamentul sistemului de trafic. Pentru a putea fi vizualizate, fiecare obiect grafic are atasata o componenta cu proprietatile de localizare în spatiul cartezian 3D. Aceasta cuprinde coordonatele de pozitionare, unghiurile Euler de rotatie și scalarea lor pe cele 3 axe.

Un aspect imporant al lucrarii sunt tehnicile de optimizare utilizate. Acestea au ca scop folosirea eficienta a microprocesorului cat și a procesorului grafic. Prin urmare ele se axeaza în primul rand pe eficentizarea algoritmilor de control, iar apoi pe nivelul de detalii prezente și reprezentarea grafica a simulării pentru a evita supraincarcarea procesorului grafic.

Pentru o simulare cat mai fidela a realitatii, toate autovehiculele sunt controlate prin intermediul unor algoritmi de comanda care executa instructiuni sincrone cu rata de afisare. Algoritmii de comanda a vehiculelor se sincronizeaza și cu semafoarele.

Lucrarea prezinta o situatie simplificata a unei zone de trafic urban; viitoarele imbunatatiri care pot fi aduse sunt: introducerea traficului pietonal și semaforizarea lui, realizarea de intersectii mai complexe cu cinci sau sase cai de acces, modificarea temporizarii semafoarelor în functie de fluxul de trafic, introducerea de vehicule speciale (ambulanta, masini de politie). Rolul ei ramane unul didactic, ea axandu-se pe controlul autovehiculelor, calculul și comanda semafoarelor, elementele grafice prezentate și pe tehnicile și algoritmii de optimizare utilizati.

Un alt punct important al proiectului reprezinta sincronizarea dintre semafoare și autovehicule. Semafoarele au astfel rolul de a opri sau lasa sa treca masinile în functie de culoarea indicatorului vizual. Pentru a simplifica algoritmii, se considea ca toate vehiculele respecta regulile de circulatie, și nu traverseaza o intersectie în cazul culorii galbele sau rosii.

Obiectivele principale

Obiectivele principale ale lucrarii sunt realizarea unui model de trafic urban și a algoritmilor și componentelor utilizate în majoritatea simulatoarelor de trafic.

Un alt punct important al proiectului il constituie metodele de optimizare grafica și computationala prezente aici. Toate aceste metode și tehnici de optimizare au ca scop reducerea timpului de executie al programului pe durata afisarii unui cadru, adica cresc performanta acestuia.

Acest proiect include proiectarea unui sistem de simulare care include comportamentul și dinamica automobilelor, interactiunile directe cu reteaua de transport și includerea de reguli de trafic. Beneficiul principal al proiectarii acestui sistem este posibilitatea de adaugare a elementelor necesare care dau simulării un nivel ridicat de realism. Combinatia acestor elemente poate fi utilizata ca baza de proiectare pentru orice model de lume virtuala. Printre avantajele acestui aspect sunt flexibilitatea și posibilitatea de extindere a proiectului.

Principala functie a sistemului de simulare este sa primeasca ca intrare retaua de trafic formata din informatiile despre rutele de acces și elementele de control (semafoarele), sa genereze dinamic automobile pe baza acestor informatii și sa afiseze simularea traficului intr-un mod corect, conform specificatiilor oferite.Portiunea din reteaua de trafic prezenta în proiect a fost generata manual, prin modelele grafice la dispozitie. Din cauza modularizarii metodelor de generare, este relativ simplu realizarea altor exemple de regiuni de trafic. Un exemplu de retea urbana generata astfel se poate observa în figura 2.1

Figura 2.1 Exemplu de retea urbana

Automobilele sunt generate în simulare în locatii special alese, corespunzatoare cu informatiile preluate de la reteaua de trafic. Astfel, se va genera un numar mai mare de vehicule pentru strazile cu mai multe cai de acces și un numar mai limitat pentru cele cu mai putine. Acest lucru aduce simularea la un nivel mai ridicat de realism și previne erorile de simulare datorata blocarii nedorite a vehiculelor. Cand simularea incepe, algoritmi predefiniti calculeaza comportamentul și actiunile fiecarui autoturism, care este animat de-a lungul caii de transport de care apartin. Pozitiile lor se modifica pe rand, creand impresia unei miscari fluide; aceasta include luarea curbelor, acelerari și franari depinzand de pozitia celorlaltor masini și tinand cont de posibilele coliziuni și opriri la semafoare.

Obiectivul principal al acestei lucrari consta în realizarea unui baze de simulare din care se pot dezvolta diverse modele de studiu pentru optimizarea controlului traficului în zonele de trafic urban. Aceasta lucrare poate fi utilizata fie pentru implementarea unor sisteme inteligente de transport în zonele de trafic, fie pentru reglarea și testarea celor existente. Prorietatile enumarate mai sus sunt asadar esentiale pentru posibilitarea simulării unor relele mai complexe, analiza unor sisteme inteligente de transport, siguranta traficului sau aplicații de protectie a mediului prin reducerea poluarii.

3. Proiectarea software

Algoritmi și tehnici de programare

Argortmii reprezinta moduri structurate de rezolvare a unor probleme prin intremediul masinilor de calcul. Ei ocupa un rol foarte important în stiinta calculatoarelor intrucat ofera solutii mai mult sau mai putin optime pentru rezolvarea și realizarea programelor software.

Motivele importantei tehnicilor de programare:

Ele pot fi transpuse usor în structuri de control și date existente în majoritatea limbajelor de nivel inalt

Ofera sablonuri clare și potrivite pentru rezolvarea unui spectru larg de probleme

Cerintele temporale și spatiale ale algoritmilor pot și analizate precis

Proiectarea algoritmilor este inclusa ca solutie optima la o multime de probleme, cateva exemple sunt programarea dinamica și divide-et-impera. Tehnicile pentru design și implementare a algoritmilor sunt folosite în mod curent în realizarea programelor software. Unele tehnici de programare sunt utilizate și în domeniul internetului, în procesele de indexare realizate de motoarele de cautare, rutarea pachetelor de date, retinerea informatiilor pe servere.

Pasii de urmat în dezvoltarea unui algoritm:

Definirea problemei

Dezvoltarea unui model

Proiectarea algoritmului

Definirea specificatiilor algoritmului

Analiza

Implementarea

Testarea programului

Realizarea documentatiei

Tabel 3.1 Algoritmi utilizati

Structuri de date

Toate informatiile din sistem sunt procesate și stocate prin intermediul structurilor de date. În simulatoarele de trafic reale sunt folosite cu precadere bazele de date. Aceste au avantajul capacitații ridicate de stocare, viteza ridicata de operare și fiabilitatea datelor inregistrate.

În cadrul stiintei calculatoarelor, o structura de data este un mod specific de retinere și organizare a informatiei intr-un modul de calcul, pentru ca aceasta sa poata fi folosita intr-un mod eficient. Mai multe tipuri de structuri de date sunt potrivite pentru diferite aplicații, iar unele au aplicabilitate doar în domenii restranse. De exemplu, arborii binari sunt des folositi pentru realizarea de baze de date, pentru compilatoare sunt de preferat hash tables pentru cautarea identificatorilor. Structurile de date ofera metode de a organiza cantitati mari de informatie eficient, cum ar fi bazele de date și serviciile de indexare pentru internet. Unele dintre metodele de poiectare și limbaje de programare pun accentul mai mult pe structurile de date, decat pe algoritmi, considerandu-le un factor cheie în proiectarea software. Încarcarea și descarcarcarea de informatie poate fi indeplinita fie în memoria principala, fie în cele secundare, insa ambele metode au avantaje și dezavantaje.

Tipuri de structuri de date:

Tipuri primitive

Boolean, poate memora trei valori: adevarat, fals sau null;

Caracter

Numar rational în simpla precizie

Numar rational cu precizie extinsa

Numar intreg

Enumarare, un set de nume unic identificate

Tipuri de structuri de date compuse

Array

Record

Union

Tagged Union

Tipuri de date abstracte

Array

Container

Dictionar

Liste

Seturi

Cozi

Stive

Arbori

Grafuri

Structurile de date se bazeaza în general pe abilitatea elementului de calcul de a reda și memora informatie în orice locatie din memoria sa, specificata printr-o adesa unica – un cod binar care poate fi la randul sau memorat și matipulat de program. Prin urmare, sirurile și obiectele sunt bazate pe capacitatea de calcul a adreselor elementelor componente cu operatii aritmetice. Unele structuri de date folosesc adresele de memorare ca sa realizeze legaturi intre elemene (spre exemplu stivele inlantuite).

Realizarea unei structuri de date necesita scrierea și implementarea unui set de proceduri care creaza și manipuleaza instantele acelei structuri. Eficienta unei structuri de date este dependenta în mod direct de aceste proceduri și nu poate fi calculata separat de acestea. Prin urmare definitia unui tip de data este o structura de memorare care este definita indirect de catre operatiile care sunt realizate asupra ei și proprietatile matematice ale acestor operatii (incluzand spatiu și timp).

Proiectarea software

Proiectarea software este procesul prin care se realizeaza un set de specificatii cu scopul de rezolva o problema utilizand un set de componente de baza care sunt supuse unor constrangeri. Proiectarea software se mai poate referi la totalitatea activitatilor de conceptualizare, implementare, testare și modificare a unor sisteme complexe cu scopul de a rezolva un set de probleme date. Proiectarea software se realizeaza inaintea implementarii efective a programelor software. Ea are ca scop documentarea și planificarea activitatilor de realizare, cu scopul reducerii timpului de executie și evitarea erorilor. Proiectarea software implica rezorvarea problemelor și planificarea unei solutii software. Aceasta include atat comonente de nivel jos cat și cele de nivel inalt.

Principiile proiectarii software ofera programatorului o fundatie de unde mai multe metode complexe pot fi aplicate. Principiile de proiectare au evoluat la:

Abstractizarea reprezinta procesul de generalizare obtinut prin reducerea continutului de informatie catre un minim necesar (relevant pentru scopul propus)

Elaborarea reprezinta dezvoltarea unei idei de tip macroscopic pe o serie de nivele avand ca destinatie atingerea de fraze de traductibile intr-un limbaj de programare utilizat. Fiecare dintre aceste nivele vor putea fi transpuse prin una sau mai multe instructiuni software. Abstractizarea și elaborarea reprezinta principii complementare

Modularizarea reprezinta divizarea unei arhitecturi software în componente independente

Arhitectura software se refera la structura generala a unui proiect informatic și la modurile în care aceasta structura ofera integritate structurala proiectului. O arhitectura de calitate superioara va genera pe termen lung rezultate pozitive din punct de vedere al performantei, calitatii, vitezei de lucru și costurilor aferente.

Ierarhia de control consta în structura unui program care reprezinta o lista de componente și din care rezulta elementele de control

Partitionarea structurala consta în divizarea verticala și orizontala a unui program. Partitionarea orizontala defineste ramuri separate o ierarhiei modularizate pentru fiecare functie majora din program. Partitionarea pe verticala se bazeaza pe ideea ca activitatile și controlul sunt distribuite pe model top-down.

Structurile de date sunt o reprezentare al legaturilor logice intre entitatile individuale de date

Procesarea software are ca principal scop prelucrarea individuala a modulelor software

Mascarea informatiei consta în totalitatea operatiilor de separare a accesului la date confidentiale intre modulele unui sistem. Înformatiile care nu sunt relevante pentru buna functionare a celorlalte module trebuie proiectate în asa fel incat sa nu poata fi accesate din afara modulului care le utilizeaza.

Diagrama UML reprezinta o reprezentare statica care reprezinta structura unui sistem informatic, aratandu-i clasele, atributele, metodele și relatiile dintre clase. Diagrama UML are o mare importanta în proiectarea software fiind utila atat în realizarea programelor, cat și în testare și depanare.

Figura 3.1 Diagrama UML a claselor

Diagrama UML de mai sus prezinta principalele clase din simulator. Alte clase care merita sa fie mentionate sunt CarAIController care asigura miscarea vehiculelor de-a lungul traseelor, WaypointCircuit care memoreaza coordonatele traseelor, Wheel care asigura functionarea corectă din punct de vedere fizic a rotilor. Dupa cum se observa, toate clasele care adauga functionalitati modelelor din simulare, extind clasa Monobehavior. Aceasta este o clasa specifica mediului Unity3D și are numeroase functii printre care functia Update, care este apelata la fiecare frame grafic. Alta proprietate importana a clasei Monobehavior este posibilitatea acesteia de a fi serializata, caracteristica esentiala în cadrul mediului de programare Unity. Înainte de fiecare compilare și executare a programului, Unity serializeaza fiecare clasa de la fiecare componenta și transforma codul sursa în byte-code.

Diagrama secventiala reprezinta o diagrama de interactiune care reprezinta ordinea și modul în care procesele din sistem interactioneaza pentru a produce rezultatul dorit. Ea contine mesajele transmise intre obiecte în timpul executiei programului. Diagrama secventiala este utila pentru documentarea cerintelor sistemului și pentru optimizarea proiectarii acestuia. În figura 3.2 se prezinta o varianta simplificata a diagramei secventiale pentru proiectul de simulare.

Figura 3.2 Diagrama secventiala

Diagrama secventiala contine patru obiecte importante pentru sistemul de simulare: managerul de simulare care este clasa principala care le initializeaza pe celelalte, un obiect de tip vehicul, un obiect de tip simulator și obiectul principal de afisare al modelelor 3D. Dupa ce managerul de simulare a initializat componeneta de afisare și a generat vehiculul, acesta incepe sa fie animat de-l lungul traseului. În momenul cand intra intr-o intersectie, vehiculul interogheaza obiectul de tip semafor pentru a determina daca trebuie sa franeze sau poate sa traverseze intersectia. În acelasi timp, sa fiecare modificare a pozitiei, el transmite automat modulului de afisare noile sale coordonate, asa ca modelul 3D este afisat corect. Dupa termiarea traseului și ajungerea vehiculului la destinatie, acesta este sters din lista, iar procesul lui intrerupt.

4. Sinteza algoritmilor de control

Noțiuni preliminare

Pentru simularea traficului urban este necesara generarea unui flux de automobile care sa se deplaseze de-a lungul unui traseu pe durata simulării în vederea colectarii datelor. Comportamentul vehiculelor trebuie specificat premergator inceperii operatiei de simulare.

Operatia de conducere a autovehiculelor este divizata în vaza de control longitudinal și lateral. Controlul longitudinal incude operatiile de accelerare și franare pe baza arhitecturii mediului inconjurator și a structurii drumului. Controlul lateral reprezinta manevrele de schimbare de banda și depasirile. Pe langa aceste operatii mai trebuie luate în considerare și evenimente precum intrarea sau parasirea intersectiilor de catre vehicule, manevrele efectuate în cadrul intersectiilor precum și alte cazuri speciale.

Modele generatoare de trafic sunt utilizate sa creeze automobile care sunt animate pe parcursul simulării de-a lungul traseurilor prestabilite. Proprietatile statice ale vehiculelor care raman constante pe parcursul simulării, sunt stabilite în procesul de generare. Pentru calcularea parametrilor variabili, spre exemplu viteza maxima sau puterea motorului, se folosesc distributii matematice.

Cea mai importanta componenta a generatorului de trafic o contrituie distributia de autovehicule pe zonele de generare și determinarea timpului intre doua generari consecutive din aceasi locatie. Pentru simulatoarele care studiaza autostrazile sau traficul urban este utilizata o generare distribuita aleatoare și în functie de capacitatea cailor de transport. Aceasta este realizata dupa distributia Poisson, adica duratele de sosire a vehiculeleor sunt idependente.

Adaptarea vitezei se refera la procesul de ajustare a vitezei pentru a tine cont de infrastructura retelei de transport, spre exemplu ajustarea vitezei la cea limita, la curbe, latimea drumului și ale proprietati ale acestuia. Controlul vitezei are o mare importanta în simularile cu model microscopic, cum este cazul celei de fata. El trabuie sa ia în considerare și interactiunile dintr autovehicule, pentru a preintampina coliziunile.

Îndiferent de tipul de drum, componeneta de control a vitezei ia în calcul viteza maxima posibila, initializata în momentul generarii. Pentru a creste astfel gradul de realism a simulării, masinile de tonaj mai ridicat vor avea atribuita o viteza maxima mai mica decat cele de tonaj mai mic.

Figura 4.1 Întersectie

În figura de mai sus se observa principalele componenete dintr-un simulator cu model microscopic. Pentru a determina pozitia semafoarelor, se utilizeaza niste senzori pentru informarea masinilor. În momentul detectarii senzorilor, masinile interogheaza starea semafoarelor. Daca culoarea acestora este verde, atunci masinile isi continua traseul.

Pentru a realiza un model de simulare mai complex, am ales reprezentarea unei intersectii semaforizate cu doua benzi de circulatie, la fel ca și în figura de mai sus. Semafoarele din intersectie sunt sincronizate intre ele, astfel ca sa fie prevenite coliziunile intre vehicule.

Argoritmi de control

Controlul autovehiculelor este o componenta importanta în cadrul simulatoarelor de trafic. De el depind în mare masura rezultatele simularilor și capacitatea simulatoarelor de a fi în concordanta cu realitatea din sistemele de trafic studiate. Acesta este în mare masura esential în toate simularile cu model microscopic.

În principal controloul autovehiculelor trebuie sa ia în calcul goemetria drumui curent, pozitia celorlalte vehicule din trafic și culorile de la semafoare. Cele mai multe modele de simulatoare implementeaza un model de control cu trei stari posibile ale masinilor:

Automobilul se deplaseaza în mode liber, urmand traiectoria prestabilita și incercand sa atinga viteza maxima propusa

Automobilul are în fata sa un alt vehicul, asa ca franeaza ca sa evite coliziunea și incearca, daca este posibil, sa depaseasca acest vehicul

Automobilul detecteaza în fata sa un obstacol sau un semafor, asa ca franeaza brusc și ramane în aceasta stare pana la eliberarea traseului.

Dupa initializarea modelelor 3D care formeaza infrastructura de trafic și initializarea coordonatelor punctelor care formeaza traseul, modelele vehiculelor sunt initializate și generate aleator în punclele de generare alese în mod special. Aceasta se realizeaza conform unei legi de dispersie și tinand cont de numarul de cai de acces din fiecare drum. Pentru ca reteaua de trafic este reprezentata ca o lista de strazi, fiecare avand doua margini, drumurile pot și alese aleator selectand un element de la un anumit index.

La fiecare initializare și generare a unui autovehicul, acesta este adaugat intr-o lista publica și unica din cadrul managerului de simulare. Vehiculele au o referinta catre traseul pe care se deplaseaza, asa ca ele pot determina în permanenta care este viitoarea locatie care trabuie atinsa. În acest fel nu este nevoie crearea unei harti globale cu toate traseele disponibile cu toate vehiculele, aceasta ar necesita o mare cantitate de memorie și ar fi dificil de parcurs și recalculat. Dupa ce masina este generata, ii este atribuita o directie printr-o alegere aleatoare intre cele doua capete ale strazii și un culoar în cazul în care strada aleasa are doua sau mai multe. Prin aceasta implementare se adauga o doza importanta de realism simulării, insa complica în aceiasi masura algoritmii de control. Aceste calcule au loc de fiecare data cand un automobil este generat și nu în fiecare frame de update grafic, asa ca nu afecteaza în mod considerabil performanta simulării.

Figura 4.2 Segmente de drum

La initializarea automobilelor este determinata și viteza maxima pentru fiecare. Viteza se modifica în functie de reteaua de trafic, la intrarea în curbe, la intrarea în intersectii și prin interactiunea cu alte vehicule, pentru a preveni coliziunile. Fiecare vehicul se caracterizeaza prin locatie curenta, directie (data de traseul pe care se afla), viteza și stare. În momentul reactualizarii pozitiei (la fiecare frame, adica aproximativ de 30 de ori pe secunda) aceasta se calculeaza în funcie de viteza și de o constanta de timp. Daca vectorul rezultat este în limitele segmentului de dreapta determinat de cele doua puncte, atunci pozitia este memorata și transmisa la modulul grafic. Daca nu este în limitele stabilite, atunci vehiculul alege sa se mute la urmatorul segment de strada. În acest fel pozitiile masinilor sunt tot timpul interpolate intre doi vetori din traseul stabilit și nu depasesc marginile lor. Pentru a simplifica acest proces, odata ce automobilul este generat, el verifica viitoarele strazile posibile pe care ar putea sa fie animat odata ce traverseaza segmentul initial, și selecteaza aleatoriu una dintre ele. În momentul schimbului, masinile isi schimba și directia de deplasare ca sa fie în concordanta cu noua strada.

Figura 4.3 Segmente de drum în cazul curbelor

Un alt aspect important al simulării consta în posibilitatea masinilor de a schimba culoarul de deplasare. Aceata proprietate a masinilor are dezavantajul de a fi complexa și de a avea cerinte mari de procesare, insa creste semnificativ nivelul de acurateze al simulării. Conditiile de schimbare a culoarului de deplasare sunt:

Autovehiculul trebuie sa fie în starea de deplasare rectilinie

Culoarul vizat trebuie sa fie liber, sa nu existe un alt automobil care sa circule pe el. Prin aceasta conditie, se asigura faptul ca nu se pot intampla coliziuni sau interblocari intre vehicule

Automobilul nu se afla intr-o intersectie, deoarece în intersectii nu sunt permise schimbarea culoarului

Automobilul nu se afla intr-o curba

Figura 4.4 Schimbarea culoarelor

În cazul în care toate condițiile sunt inteplinite, atunci toate vehiculele au o sansa aleatoare de a-și schimba culoarul curent. Sansa de schimbare creste odata cu timpul pana la un maxin de 10%, iar apoi se reseteaza la minim 1% în cazul în care vehiculul isi schimba intradevar culoarul.

La schimbarea culoarului se intampla un lucru similar cu cel de la depasirea unui segment de strada, se modifica culoarul curent al vehiculului și acesta isi modifica directia de deplasare catre punctul final al noului segment de strada.

Figura 4.5 Evitarea coliziunilor

O componenta cheie a simulării traficului este prevenirea coliziunilor. Cel mai simplu caz de coliziune se realizeaza intre acele vehicule care sunt pe acelasi culoar de drum și se deplaseaza în aceiasi directie. Fiecare masina are un anumit spatiu în fata ei rezervat, care este direct proportional cu viteza curenta. Cand doua masini se deplaseaza pe acelasi segment de strada, iar vehiculul din spate are viteza mai mare decat cel din fata, cel din spate isi va modifica incet viteza, pana cand masina din fata nu mai este în spatiul rezervat. În acest fel tot timpul va exista o distanta intre doua masini consecutive, asa cum se observa în figura de mai sus. Masina din dreapta nu are nici o masina în vecinatate, asa ca ea accelereaza pana la viteza maxima. Cele doua masini invecinate, merg la viteze egale. În plus, masina de la mijloc are o sansa mai mare acum sa schimbe culoarul ales, daca are posibilitatea.

5. Implementarea

Elementelele principale care stau la baza oricarui sistem de simulare sunt retaua de trafic cu diferite strazi și cai de acces, automobile și elemente de control al traficului.

Tabel 5.1 Elemente de simulare

Cea mai importanta componenta a sistemului de simulare este Simulation Manager. Aceasta componenta monitorizeaza fiecare automobil generat în cadrul simulării și analizeaza date statistice privitoare la acesta. Fiecare automobil memoreaza în permanenta locatia curenta, directia de deplasare, viteza și sarea în care se afla. Smularea poate fi recalculata, un proces care presupune deplasarea tuturor masinilor un pas în fata pe directia lor curenta de deplasare cand este executata. Dupa ce toate locatiile au fost recalculate, simularea se conecteaza la procesorul grafic, care preia datele memorate și afiseaza toate elementele grafice, cum ar fi reteaua de trafic și automobilele. Pentru afisarea automobilelor, componenta de afisare parcurge lista cu toate vehiculele și afiseaza modelul grafic corespunzator, asa cum este prezentat în figura 5.1.

Figura 5.1 Bucla de simulare

Diagrama de mai sus arata primul pas din simulare, care este initializarea programului software. Aceasta presupune modelarea retelei de trafic și a elementelor de control și generarea automobilelor în locatii prestabilite. Locatiile automobilelor sunt calculate relativ la traseele lor deoarece acestea sunt generate în puncul de start al traseelor. Pozitia vehiculelor este transmisa la modulul de afisare, iar modelele grafice sunt proiectate pe ecran. Sistemul de simulare intra astfel intr-o bucla de animatie unde componenta de afisare cere actualizarea locatiilor automobilelor. Dupa actualizare, componenta de afisare parcurge lista de vehicule și le redeseneaza la pozitiile noi. Acest porces continua pana simularea se termina.

Sistemul este implementat exclusiv intr-un mediu de simulare 3D, insa se poate transpune cu usurinta intr-un mediu 2D. Odata realizata, simularea utilizeaza mediul Unity3D pentru afisarea corectă a tutror modelelor 3D. Înteractiunea dintre vehicule și sistemele de control de trafic este realizata dinamic de algoritmii de control.

Dupa ce strunctura retelei de trafic este initializata, sunt generate elementele de control al traficului, respectiv semafoarele. Din cauza complexitatii realizarii semafoarelor pentru fiecare intersectie, s-a ales ca numai cateva intersectii sa fie semaforizate. Printr-un algoritm se parcurge lista de segmente de strazi și se determina pozitiile senzorilor pentru semafoare. Fiecare vector din lista poate sa determine strada de care apartine, asa ca o intersectie cu patru cai va fi gasita la aceea locatie care este prezenta de patru ori în lista.

Automobilele prezente în simulare sunt caracterizate de pozitie, directie de deplasare, viteza și stare (fie ca este de repaus sau de miscare rectilinie). Modelarea lor este realizata cu ajutorul diverselor componente, care sunt separate în scripturi/clase distincte. Aceasta tehnica de separare a functionalitatilor în scripturi diferite se numeste encapsulare și este una dintre cele mai puternice și flexibile metode de programare pe care mediul Unity le ofera.

Proprietatile care definesc scriptul CarAIControl sunt:

Acest script are principalul rol, dupa cum se observa din proprietati, sa controleze fiecare automobil astfel incat sa isi mentina traseul stabilit. Prin variabila de „wander”, controlul este mult mai realist și mai putin robotic, masina se poate indeparta aleator o anumita distanta de la traseu.

Functia de update a scripului este prezentata pe scurt mai jos:

În prima parte a functiei, se verifica daca automobilul este în starea de miscare, iar în cazul în care este atunci se calculeaza locatia tinta în functie de traseul stabilit.

Uramtoarea parte are ca scop evitarea altor masini din trafic, și oprirea în caz de coliziune.

Pentru implementarea traseelor se utilizeaza urmatorul script:

6. Tehnici de optimizare utilizate

Optimizarea elementelor grafice

Performanta este una dintre caraceristicile critice ale oricarui program informatic, iar simulatoarele nu fac exceptie de la acesta regula. Optimizarea elementelor grafice reprezinta totalitatea tehnicilor de programare utilizate în scopul maximizarii vitezei de afisare a elementelor grafice și de reducere a consumului de memorie.

Componentele grafice ale programelor pot fi costisitoare în cele doua sisteme ale computerului: procesorul grafic sau GPU sau procesorul central sau CPU. Prima regula a optimizării consta în localizarea probelemei de performanta, deoarece strategiile de optimizare pentru GPU sau CPU sunt foarte diferite și pot fi chiar opuse; de obicei de face un compromis intre nivelul de munca realizat de CPU și de GPU.

Cea mai simpla verificare a faptului ca GPU este componenta cea mai solicitata este executarea simulării la o rezolutie mai redusa; în cazul în care aceasta se executa mult mai performant, atunci problema este în mare masura grafica, iar efortul de optimizare trebuie concentrat pe modelele 3D, shaders, surse de lumina, particule și alte efecte grafice. Pentru verificarea procesorului central se verifica numarul de obiecte care trebuie sa fie afisate la fiecare frame, numar care se defineste ca draw calls. Acest numar trebuie sa fie în jur de cateva mii pentru programele care se executa pe PC și de ordinul sutelor pentru aplicatiile mobile. Daca numarul de draw calls depaseste aceste limite, atunci trebuie sa ne axam eforturile pentru reducerea lui. Aceasta se poate realiza prin reducerea numarului de obiecte vizualizate sau combinarea texturilor obiectelor în atlase mai mari.

Figura 6.1 Combinarea texturilor în atlase

Bineinteles ca motivele pentru care performanta unui program software este sub un nivel limita pot sa fie mult mai multe și mai complexe decat cele prezentate mai sus. Cateva dintre problemele tipice aplicatiilor grafice sunt:

Afisarea modelelor grafice nu este o problema majora, nici pentru procesorul grafic nici pentru cel central. Codul scris și algoritmii folositi în schimb pot sa produca scaderi de performanta majora.

Procesorul grafic are prea multe noduri din modelele grafice de calculat. Numarul maxim de noduri care pot și procesate fara sa afecteze drastic performanta depinde de tipul GPU și de complexitatea shader-elor. În mod normal nu trebuie utilizate mai mult de o suta de mii de noduri pentru device-urile mobile și nu mai mult de cateva milioane pentru aplicatiile care se executa pe calculatoare.

Procesorul central are prea multe noduri de procesat. Aceasta problema apare în cazul obiectelor texturate, simulator de haine, particule animate, etc.

Un anumit script are o problema de performanta. Aceast aspect este probabil cel mai greu de depistat, pentru ca poate fi o problema de calcul, fie o problema de memorie.

Pentru depistarea problemelor de performanta, mediul Unity pune la dispozitie o aplicatie de depanare a programelor software denumita Unity Profiler. Aceasta calculeaza și reprezinta cat timp este consumat în portiuni diferite ale programului.

Figura 6.2 Unity Profiler

Unity Profiler are rolul de optimizare al programelor realizate în Unity. El evidentiaza acele componenete care sunt foarte costisitoare pentru procesorul grafic și cel central. De asemenea el are abilitatea de a intregistra informatiile și sa le afiseze pe un timeline; în acest mod se pot observa și în ce momente de timp se produc cele mai semnificative scaderi de performanta. Pentru a putea intregistra aceste informatii, Unity Profiler trebuie sa fie executat simultan cu programul studiat.

Este important de retinut ca Unity Profiler trabuie sa analizeze dinamic performanta programelor. Analiza lor nu afecteaza în schimb performanta existenta a programelor. Pentru optimizare este important de retinut procentul de timp în anumite astpecte din executie. De asemenea se pune accentul pe acele portiuni care dureaza cea mai mare portiune de timp dintr-un ciclu de procesare. Dupa realizarea modificarilor necesare în acele zone se compara rezultatele cu cele de dinainte. Cateodata modificarile facute pentru imbunatatirea performantei au un efect negativ asupra timpului de executie, asa ca trebuie sa revenim la versiunea precedenta.

Pentru afisarea fiecarui obiect pe ecran, procesorul central trebuie sa proceseze numeroase lucruri care caracterizeaza fiecare obiect, cum ar fi luminle care sunt în raza obiectului, setarea shader și parametrii shader-urilor, trimiterea de comenzi de desenare catre driver-ul grafic, care trimite la randul sau comenzi catre placa grafica. Toate acestea se realizeaza pentru fiecare obiect, asa ca, daca sunt multe obiecte care trebuie randate, performanta poate sa scada.

Figura 7.3 Modele 3D simplificate

Spre exemplu, este mult mai usor de randat o mie de triunghiuri intr-un singur model 3D dacat o mie de triunghiuri independente. Pentru procesorul grafic, cele doua scenarii sunt similare, insa pentru CPU diferenta este foarte mare. Prin urmare, cateva metode de reducere a incarcarii procesorului central sunt:

Combinarea obiectelor apropiate intr-un singur model grafic, fie manual, fie utilizand gruparea automata realizata de Unity.

Utilizarea a cat mai putine materiale pentru obiecte

Combinarea texturilor mici în atlase de dimensiuni mari

Reducerea efectelor care fac ca obiectele sa fie randate de mai multe ori, cum ar fi reflexii, umbre, straluciri.

Pentru a creste performanta este important sa grupezi obiectele 3D impreuna, în asa fel incat fiecare grup sa contina cateva sute de triunghiuri și utilizeaza un singur material sau textura pentru intregul model. Daca combinam doua obiecte, dar acestea nu au material comun, atunci cresterea de performanta nu se realizeaza.

În cazul în care dorim optimizarea executiei procesorului grafic atunci trebuie sa urmam doua reguli de baza: sa nu utilizam mai multe triunghiuri în modelele 3D decat este necesar și sa incarcam sa folosim cat mai putin maparea UV și muchiile tari (dubluri de noduri). Trebuie sa fim atenti la faptul ca numarul de muchii și noduri pe care placa grafica trebuie sa le proceseze este mai mare dacat cel calculat de programele de modelare 3D. Acestea afiseaza numai numarul de noduri distincte dintr-un model grafic, insa GPU trebuie uneori sa separe modelul în portiuni mai simple de randat, asa ca rata de muchii procesate creste.

Figura 6.4 Optimizarea modelelor 3D

Optimizarea algoritmilor software

Optimizarea codului scris este o parte importanta a optimizării unei aplicații în Unity. Cateva dintre metodele de optimizare a scripturilor sunt prezentate mai jos:

De obicei problemele de performanta apar atunci cand se fac prea multe calcule în fiecare frame grafic

Pentru optimizarea calculelor, am realizat functia astfel:

Cu toate ca arata mai complicat, în realitate este mult mai clar, iar performanta este mult mai buna în al doilea caz. Calculele pentru traiectoria masinii sunt la fel apelate, insa nu la fiecare frame, iar calculele pentru locatia de final nu sunt apelate decat la inceput pentru initializare.

Pentru optimizarea memoriei și a performantei se utilizeaza apelarea garbage collector. Acesta este apelat în mod automat de sistem cand memoria este plina, insa este de preferat sa fie apelat manual în anumite momente. Pentru aceasta se utilizeaza scriptul urmator:

Aceasta metoda nu imbunatateste timpul de executie, dar reduce problemele de memorie și eventualele scaderi de performanta.

Folosirea corectă a StringBuilder. StringBuilder este o clasa speciala C# utilizata pentru concatenarea sirurilor de caractere. Cu toate ca ofera performanta în plus, se justifica utilizarea ei numai în cazul sirurilor de caractere foarte mari.

Compararea sirurilor de caractere non-case-sensitive.

Pentru o performanta mai buna se incearca inlocuirea clasei ArrayList cu List<>. ArrayList este utila atunci cand dorim sa memoram mai multe obiecte de tipuri diferite în acelasi sir. În cazul în care tipul obiectelor este identic, atunci este indicata utilizarea clasei List<>.

Avantajele optimizării

Obiectivul principal în scrierea unui program este ca acesta sa functioneze corect în toate circumstantele posibile. Un program software care se executa rapid dar ofera rezultate incorecte nu are nici un scop practic. Programatorii trebuie sa scrie un cod clar și concis, nu doar ca ei sa-l poata intelege usor, dar și ceilalti programatori sa-l poata analiza, intelege și extinde daca este cazul.

Pe de alta parte, sunt numeroase cazuri în care viteza cu care se executa un program este foarte importanta. Daca acel program trebuie sa proceseze modele 3D sau pachete de transfer în timp real, atunci un program care se executa lent nu va avea functionalitatea dorita. Cand o sarcina este atat de complexa, incat dureaza zile sau saptamani pentru a fi terminata, o imbunatatire cu doar 15% a timpului are un efect semnificativ și merita toata atentia.

Scrierea unui program eficient consta în mai multe etape:

Alegerea algoritmilor și structurilor de date potivite pentru aplicatia dorita. Pentru structurile de date trebuie sa avem în vedere relatia dinte performanta și dimensiunea memoriei ocupate și sa facem cel mai potrivit compromis intre cele doua.

Este important sa utilizam cod pe care compilatorul poate sa-l optimizeze intr-un mod eficient. Pentru acest motiv, trebuie sa intelegem capacitatea și limitiarile optimizării realizate de compilator. Modificari minore în program pot sa determine schimbari majore în modul de compilare. În acest sens unele compilatoare sunt mai eficiente dacat altele.

Divizarea calculelor în sub-sarcini ce pot fi executate intr-o arhitectura multi-thread. În cazul utilizarii acestei metode este important ca fiecare fir sa se execute cu performanta maxima. De asemenea trebuie sa rezolvam și problemele de sincronizare intre fire, ceea ce duce uneori la scaderea performantei.

Figura 6.5 Unity Profiler

Pentru a aplica tehnicile de optimizare prezentate mai sus trebuie sa luam în considerare cum va fi utilizat programul și care sunt factorii cheie care il afecteaza. În general programatorii trebuie sa faca un compromis intre cat de usor este un program de realizat și intretinut și cat de eficient se executa. La nivel algoritmic, o simpla sortare a unei liste poate sa fie programata în cateva minute, insa un algoritm foarte eficient de sortare specific contextului poate sa dureze o zi sau mai multe pentru a fi implementat. La nivel de cod, multe dintre optimizarile de nivel jos tind sa reduca lizibilitatea codului și flexibilittea, facand programul mult mai susceptibil la erori și mult mai dificil de modificat sau extins. Pentru acele portiuni de cod care vor fi executate în mod repetat intr-un mediu unde performanta este importanta, optimizarea excesiva este singura metoda acceptabila. O provocare continua este mentinerea unui nivel de lizibilitate și intelegere a codului desi folosim aceste transformari excesive.

Am aratat mai sus un numar de metode pentru imbunatatirea performantei programului de simulare. În mod ideal, un compilator ar trebui sa fie capabil sa primeasca orice program vrem noi sa scriem, și sa genereze un program la nivel masina cel mai optimizat posibil și cu un comportament dorit. Compilatoarele moderne (cum este cel utilizat pentru C#) folosesc metode complexe de analiza și optimizare, și se imbunatatesc în mod continuu. Însa pana și cele mai eficiente compilatoare au unele limitari, cum ar fi acele aspecte ale programelor care depind de mediul de executie. Singura solutie este asistarea compilatoarelor prin scrierea de cod care poate fi optimizat usor.

Un prim pas în optimizare este eliminarea portiunilor care nu sunt necesare, facand codul sa isi indeplineasca sarcinile cu cea mai mare performanta. Acest pas include eliminarea apelurilor catre functii care nu sunt necesare, potiuni de cod care nu vor fi apelate din cauza condițiilor impuse, variabile neutilizate. Aceste optimizari au avantajul ca nu depind de proprietatile device-ului de care apartin.

Pentru a maximiza performanta unui program atat programatorul cat și compilatorul necesita un model a device-ului tinta, care specifica cum sunt procesate și temporizate caracteristicile diferitelor operatii. Spre exemplu compilatorul trebuie sa cunoasca datele de temporizare pentru a alege intre o operatie de multiplicare sau o operatie de shiftare pe biti și adunare. Computerele moderne folosesc tehnici complicate pentru procesarea programelor la nivel masina, executand multe instructiuni în paralel și în ordini diferite decat cele din program. Programatorii trebuie sa inteleaga cum functioneaza aceste procese și sa fie capabili sa ajusteze programele lor pentru viteze maxime.

7. Posibilități de dezvoltare ulterioară

Aceasta lucrare functioneaza în parametrii ceruti, insa prezinta doar functionalitatea de baza a unui simulator de trafic. Asadar exista numeroase posibilități de extindere și imbunatatire. Sarcina cu cea mai mare prioritate pentru continuarea proiectului ar fi integrarea unui oras complex cu modele 3D în Unity pentru simularea traficului de pietoni. De asemenea ar fi de preferat și introducerea mai multor modele de masini, în special cele cu prioritati deosebite cum sunt masinile de politie sau de ambulanta.

Un alt mod de extindere al lucrarii ar fi implementarea unor algoritmi de control de trafic pentru semafoare. Un obiectiv interesant de studiat ar fi calcularea temporizarii semafoarelor în functie de fluxul de trafic și realizarea unor regulatoare specifice. În acest domeniu posibilitatile sunt foarte numeroase și complexe, de la algoritmi fuzzy pana la genetici.

Autovehiculele existente în simulare pot fi usor imbunatatite prin adaugarea luminilor de semnalizare și extinderea algoritmilor de control. Autovehiculele pot de asemenea sa interactioneze cu pietonii la un nivel mult mai detaliat. De asemenea, datele provenite de la vehicule ar putea fi inregistrate și stocate intr-o baza de date. Statisticile generate astfel pot constitui o baza de testare pentru aplicatiile de control de trafic reale.

Încluderea unor linii pentru autobuz sau alte mijloace de transport în comun este un alt pas de extindere realizabil. Aceste linii trebuie sa fie cu acces interzis sau restrictionat pentru celelalte vehicule participante la trafic.

Colectarea datelor este un punct principal abordat de toate simulatoarele de trafic, asa ca eventualele extinderi se pot baza pe ea. Datele care rezulta în urma diferitelor simulari reprezinta principalul scop al programelor de simulare. Scopurile principale sunt evitarea interblocajelor, depistarea zonelor care incetinesc fluxul de trafic, depistarea erorilor în sistemele de control.

Un alt aspect important de realizat este o interfata grafica cu utilizatorul. Aceasta trebuie sa fie intuitiva și sa permita atat introducerea de parametrii de simulare, incarcarea dinamica a rețelelor de trafic, reglarea în detaliu a componentelor, cat și vizualizarea datelor obtinute în urma executiei. Simulatorul trebuie sa aiba posibilitatea de a fi pus în starea de pauza, pentru o atenta verificare a datelor și locatiilor autovehiculelor. Mediul Unity permite toate aceste modificari fara prea mare efort.

Pentru o simulare cat mai realista nu trebuie uitate și alte elemente grafice care cresc nivelul de detaliu, cum ar fi cladiri mai diversificate, semne de circulatie și alte elemente de control al traficului.

Analiza sigurantei rețelelor de trafic și calcularea nivelelor de poluare reprezinta o alta posibila imbunatatire ce poate fi adusa lucrarii. Majoritatea simulatoarelor de trafic integreaza deja toate aceste aspecte.

8. Concluzii

Simularea pe calculator se dovedeste a fi o unealtă foarte des utilizata pentru analiza sistemelor dinamice complexe. Aceasta lucrare prezinta un model de simulator de trafic microscopic realizat în mediul de programare Unity3D cu scopul de a exemplifica avantajele proiectarii și testarii sistemelor de control de trafic prin intermediul simulatoarelor.

Lucrarea incepe cu o scurta introducere în caracteristicile simulatoarelor de trafic și a importantei lor pentru sistemele inteligente de trafic. Asa cum am aratat mai sus, proiectul poate fi extins și dezvoltat intr-un simulator de trafic complet. Tot în introducere este prezentat pe scurt mediul de programare Unity impreuna cu limbajul de nivel inalt C#. Acest mediu de programare permite cu usurinta realizarea de animatii 3D și implementarea algoritmilor de control prin scripturi. Proiectul contine la nivel grafic numeroase modele 3D utilizate pentru reprezentarea diverseleor elemente, cum ar fi reteaua de trafic, automobilele, cladirile și sistemele de control de trafic.

Scopul acestui proiect, la fel ca și scopul simulatoarelor de trafic existente este proiectarea unui sistem de trafic cat mai fidel realitatii. Acest lucru se realizeaza prin algoritmii de control al vehiculeleor și prin implementarea prin scripturi a regulilor principale din trafic. Lucrarea prezinta și explica în detaliu nu numai scripturile și algoritmii utilizati, dar și modurile de proiectare și justificarea lor. Dupa initializarea traseelor și a retelei de trafic, manager-ul de simulare se ocupa de generarea și initializarea autovehiculelor. Acestea sunt animate de-a lungul cailor de acces cu ajutorul scripturilor. Prin aceste scripturi se asigura evitarea coliziunilor, respectarea directiei corecte și a regulilor de circulatie, oprirea la semafoare. Se realizeaza astfel o simulare a traficului cu un nivel mare de detaliu.

Pe langa controlul autovehiculelor, este important de mentionat implementarea algoritmilor de comanda a semafoarelor. Acestea au rolul de a opri fluxul de trafic în intersectii pentru a se evita coliziunile, și reprezinta un important punct de studiu în cadrul simulatoarelor.

Un punct esential al acestui proiect sunt prezentarea tehnicilor de optimizare, deoarece în aplicatiile grafice, performanta animatiilor este prioritara. În cazul aplicatiilor realizate în mediul Unity, toate metodele de optimizare se impart în doua directii: optimizarea modelelor grafice și optimizarea algoritmilor software. Prima regula de optimizare este utilizarea profiler-ului, și determinarea portiunilor ineficiente din program. Pentru cresterea performantei afisarii se incearca simplificarea modelelor 3D și renuntarea la efecte, materiale și particule care solicita procesorul central. Optimizarea algoritmilor este insa mult mai complicata. În general se evita calculele complexe realizate la fiecare reafisare, și se utilizeaza structuri de date potivite pentru contextul dat.

9. Bibliografie

[1] J.C. Williams, “Macroscopic Flow Models. în Traffic Flow Theory”, 1996

[2] F.L. Hall, "Traffic stream characteristics", în Traffic Flow Theory, 1996

[3] R.W. Rothery, “Car Following Models în Traffic Flow Theory”, 1996

[4] Fen Fei Yang, Joe Weihoffer, „Vehicle traffic simulation”, 2010

[5] Jeffrey J. McConnell, „Computer Graphics: Theory Înto Practice”, Jones & Bartlett Publishers, 2006

[6] David Salomon, „Computer graphics and geometric modeling“, 1999

[7] S.A. Boxill, L. Yu, "An Evaluation of Traffic Simulation Models for Supporting ITS Development", 2000

[8] docs.unity3d.com/412/Documentation/ScriptReference/index.Performance_Optimization .html

Bibliografie

[1] J.C. Williams, “Macroscopic Flow Models. în Traffic Flow Theory”, 1996

[2] F.L. Hall, "Traffic stream characteristics", în Traffic Flow Theory, 1996

[3] R.W. Rothery, “Car Following Models în Traffic Flow Theory”, 1996

[4] Fen Fei Yang, Joe Weihoffer, „Vehicle traffic simulation”, 2010

[5] Jeffrey J. McConnell, „Computer Graphics: Theory Înto Practice”, Jones & Bartlett Publishers, 2006

[6] David Salomon, „Computer graphics and geometric modeling“, 1999

[7] S.A. Boxill, L. Yu, "An Evaluation of Traffic Simulation Models for Supporting ITS Development", 2000

[8] docs.unity3d.com/412/Documentation/ScriptReference/index.Performance_Optimization .html